Modelle und Methoden zur ourenplanungT mit

Einleitung und Motivation Literatur Beiträge der Dissertation Fazit und Ausblick

Modelle und Methoden zurTourenplanung mit Fahrzeugsynchronisation

Dorota Sªawa Ma«kowska

Martin-Luther-UniversitätHalle-Wittenberg

16. Doktorandenworkshop NordostClausthal, 22. Mai 2014

Das Forschungsprojekt wird von der DFG �nanziert, Projektnummer B02110263.

Dorota Sªawa Ma«kowska Tourenplanung mit Fahrzeugsynchronisation 1


Agenda

1 Einleitung und Motivation

2 Themenbezogene wissenschaftliche Literatur

3 Beiträge der Dissertation

4 Zusammenfassung und Ausblick



Agenda







Tourenplanungsprobleme

klassisches Tourenplanungsproblem (Vehicle Routing Problem)

Finde Touren für homogene Fahrzeuge, die an einem Depot stationiert sind, sodassjeder Kunde genau einmal besucht wird, mit einem Ziel z. B. der Minimierungder zurückgelegten Strecke.

Zeitfenster

mehrere Depots

heterogener Fuhrpark

Rücktransport

mehrfacher Fahrzeugeinsatz

Pickup and Delivery

Split Delivery

...Übersicht: Toth and Vigo (2002); Golden et al. (2008); Repoussis and Gounaris (2013)






Zeitfenster

mehrere Depots


Rücktransport


Pickup and Delivery

Split Delivery







Zeitfenster

mehrere Depots


Rücktransport


Pickup and Delivery

Split Delivery




Fahrzeugsynchronisation

VRP mit Synchronisation

Es gibt Knoten, die von mehreren Fahrzeugen besucht werden (können).

junges Forschungsgebiet - seit ca. 10 Jahren

keine einheitliche Systematik

e�ektive Lösungsmethoden und Planungstools für die Praxis sind gefragt



Mobile P�egedienste

Operations Management: P�egedienst, Bredström and Rönnqvist (2008)

einfacher Service:

synchronisierter Service:

p zeitgleicher Service:

ah

asdddddszz zeitversetzter Service:



Beispiele (Forts.)

Transportwirtschaft, Begegnungsverkehr, Kunze et al. (2012)

- Fahrzeuge tauschen die Ladung aus

- Synchronisationspunkte be�nden sich i. d. R. zentral

E�ektive Nutzung der Ressourcen, z. B.:

Reduktion der Fahrleistung

bessere Nutzung der Fahrereinsatzzeiten



Weitere Beispiele

Forstwirtschaft, Waldernte, z. B. Flisberg et al. (2007)

Abfallentsorgung, z. B. Del Pia and Filippi (2006)

Aufstellen von DHL-Packstationen, z. B. Hombrink (2008)



Agenda







State of the art

Übersichtsartikel über Synchronisationsanforderungen in VRP, Drexl (2012)

Typ Kriterien Tourenplanungsprobleme (Bsp.)

operationTätigkeiten verschiedener Subjekte müssen anbestimmten Orten synchronisiert werden

2eVRP, PDVRP,...

movementBewegungsrichtung muss angeglichen werden(z. B. Anhänger an Fahrzeugen)

TTVRP, DARP,...

loadTransportmengen müssen synchronisiert werden(z. B. Be-, Ent- und Umladung)

SDVRP,...

resourceKapazitätsrestriktionen dürfen nichtüberschritten werden, z. B. #Dockingstationen

CVRP,...



Klassi�kation der Fahrzeugsynchronisationsanforderungen

Zeitliche Synchronisation

zeitgleich zeitversetzt

RäumlicheSynchroni-sation

ortsgebunden Typ I Typ II

ortsungebunden Typ III Typ IV



Agenda







Literaturstudie

Aufsatz AnwendungSynchronisationstyp

I II III IV

Haase et al. (2001) Busfahrereinsatzplanung ×Freling et al. (2003) Busfahrereinsatzplanung ×Li et al. (2005) Hafentechnikereinsatzplanung ×Meisel and Kopfer (2014) passive/aktive Transportmittel ×Lee et al. (2006) cross-docking ×Yu and Egbelu (2008) cross-docking ×Wen et al. (2009) cross-docking ×Eveborn et al. (2006) P�egedienste × ×Bredström and Rönnqvist (2008) P�egedienste, Waldernte × ×Rasmussen et al. (2012) P�egedienste × ×Kergosien et al. (2009) P�egedienste × ×Mankowska et al. (2011) Theorieansatz × ×Goel and Meisel (2013) Wartungsarbeiten × ×Mankowska et al. (2014) P�egedienste × ×Mankowska (2014) P�egedienste × ×Balsliemke (2004) Begegnungsverkehr ×Del Pia and Filippi (2006) Müllabfuhr ×Weise et al. (2009) Begegnungsverkehr ×Mankowska et al. (2012a) Theorieansatz ×Mankowska et al. (2012b) Aufstellen von Packstationen × ×Mankowska et al. (201x) Theorieansatz (×) (×) × ×



Übersicht über die Beiträge

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2011): Modelling the Synchronization of Transport Means in Logistics Service Operations, in: Böse, J. W. et al. (Hrsg.): ICCL 2011, Lecture Notes in Computer Science 6971, 74-85

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2012): Spatial and temporal synchronization of mobile servers in service networks, in: Klatte, D. et al. (Hrsg.): OR Proceedings 2011, 263-268

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2012): A Vehicle Routing Problem with Cargo Transfer Options, in: Günther, H.-O. et al. (Hrsg.): LOGMS 2012, 417-427

Mankowska, D. S.; Meisel, F.; Bierwirth, C. (2014): The Home Health Care Routing and Scheduling Problem with Interdependent Services, Health Care Management Science 17(1), 15-30

Mankowska, D. S. (2014): Synchronization in Vehicle Routing: Benders' Decomposition for the Home Health Care Routing and Scheduling Problem, in: Thoben, H.-D. et al. (Hrsg.): Dynamic in Logistics, Lecture Notes in Logistics, im Druck

Typ I Typ II

Typ III Typ IV

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (201x): Vehicle Routing Problem with Synchronisation at Variable Points, work in progress

ortsgebunden

ortsungebunden




Übersicht über die Beiträge

1

2

3

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2011): Modelling the Synchronization of Transport Means in Logistics Service Operations, in: Böse, J. W. et al. (Hrsg.): ICCL 2011, Lecture Notes in Computer Science 6971, 74-85

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2012): Spatial and temporal synchronization of mobile servers in service networks, in: Klatte, D. et al. (Hrsg.): OR Proceedings 2011, 263-268

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (2012): A Vehicle Routing Problem with Cargo Transfer Options, in: Günther, H.-O. et al. (Hrsg.): LOGMS 2012, 417-427

Mankowska, D. S.; Meisel, F.; Bierwirth, C. (2014): The Home Health Care Routing and Scheduling Problem with Interdependent Services, Health Care Management Science 17(1), 15-30

Mankowska, D. S. (2014): Synchronization in Vehicle Routing: Benders' Decomposition for the Home Health Care Routing and Scheduling Problem, in: Thoben, H.-D. et al. (Hrsg.): Dynamic in Logistics, Lecture Notes in Logistics, im Druck

Typ I Typ II

Typ III Typ IV

Mankowska, D. S.; Bierwirth, C.; Meisel, F. (201x): Vehicle Routing Problem with Synchronisation at Variable Points, work in progress

ortsgebunden

ortsungebunden




Ortsgebundene Synchronisation (Typ I und II)

Folgende Entscheidungen sind zu tre�en:

Für Kunden, die keine Synchronisation erfordernWelche Fahrzeuge befahren welche Kunden?Wann fangen die Fahrzeuge an, die Services zu erbringen?

Für Kunden, die Synchronisation erfordern:Welche Fahrzeuge nehmen an Synchronisation teil?Wann beginnen die zeitgleichen und zeitversetzten Besuche?



Home Health Care Routing and Scheduling Problem

Anwendungsfall: mobile P�egedienste

beliebige Anzahl von unterschiedlich quali�zierten Mitarbeitern

Mitarbeiter fahren zu den Patienten mit dem Auto, Fahrrad, etc.

einfacher (single) Service vs. synchronisierter (double) Service

zeitgleich

zeitversetzt

Verspätung zugelassen (keine Verfrühung)

minimale und maximale Zeitabstände zwischen den Diensten müsseneingehalten werden



Mathematische Modellierung für HHCRSP

Es werden drei Ziele verfolgt:

die Minimierung der gesamten Länge der zurückgelegten Strecke

die Minimierung der gesamten Verspätung

die Minimierung der maximalen Verspätung (Fairness)

Entscheidungsvariablen:

xijvs binär; 1, wenn v direkt von i zu j fährt, um dort Service s zu erbringen

tivs kontinuierlich; Anfangszeit beim Patienten i von Mitarbeiter v von Service s

Synchronisation: Routing ∑v∈V

∑j∈C0

avs · xjivs = ris ∀i ∈ C, s ∈ S

Synchronisation: Scheduling

tiv′s′ − tivs ≥ δmini −M(2−

∑j∈C0

xjivs −∑j∈C0

xjiv′s′ ) ∀i∈Cd , v ,v ′∈V, s, s′∈S: s< s′

tiv′s′ − tivs ≤ δmaxi −M(2−

∑j∈C0

xjivs −∑j∈C0




Mathematische Modellierung für HHCRSP

Es werden drei Ziele verfolgt:

die Minimierung der gesamten Länge der zurückgelegten Strecke

die Minimierung der gesamten Verspätung

die Minimierung der maximalen Verspätung (Fairness)

Entscheidungsvariablen:

xijvs binär; 1, wenn v direkt von i zu j fährt, um dort Service s zu erbringen

tivs kontinuierlich; Anfangszeit beim Patienten i von Mitarbeiter v von Service s

Synchronisation: Routing ∑v∈V

∑j∈C0

avs · xjivs = ris ∀i ∈ C, s ∈ S

Synchronisation: Scheduling

tiv′s′ − tivs ≥ δmini −M(2−

∑j∈C0

xjivs −∑j∈C0


tiv′s′ − tivs ≤ δmaxi −M(2−

∑j∈C0

xjivs −∑j∈C0




Metaheuristische Lösungsmethode für HHCRSP

Adaptive Variable Neighborhood Search:

basiert auf Variable Neighborhood Search, Hansen and Mladenovi¢ (2001)

vermeidet das Verbleiben im lokalen Optimum durch systematische Änderungder Nachbarschaftsstruktur in der lokalen Suche

vorgegebene Reihenfolge der Nachbarschaften

bessere Lösung gefunden? Neustart mit der ersten Nachbarschaft

Terminierung, wenn ein Abbruchkriterium erfüllt ist

unsere adaptive Komponente: Ranking der Nachbarschaften nachabsteigender Leistung in den ersten α Iterationen der lokalen Suche



Lösungsrepräsentation

Eigenschaften der Lösungsrepräsentation:

zeigt die Reihenfolge der Patientenbesuche für jeden Mitarbeiter

bildet alle Kombinationen von Zuordnungen Patient↔Mitarbeiter ab

vermeidet Deadlocks

ermöglicht eine e�ziente iterative Berechnung der Servicestartzeiten

vereinfacht die De�nition von Nachbarschaften für lokale Suchverfahren



Erö�nungslösung und Nachbarschaften

Erö�nungslösung (slack-based greedy rule)Zuordnung sortierten Patienten nach li den Mitarbeiter wie folgt:

single service: 1 quali�ziert, früheste Ankunftszeitdouble service: 2 quali�zierte Mitarbeiter, früheste Ankunftszeiten

8 Nachbarschaften (4 für single service; 4 für double service)



Sensitivitätsanalyse

Bis zu 20% hat Cplex einen leichten Vorteil gegenüber AVNS.

Mit steigender Komplexität versagt Cplex.



Sensitivitätsanalyse

Bis zu 20% hat Cplex einen leichten Vorteil gegenüber AVNS.

Mit steigender Komplexität versagt Cplex.



Exakte Lösungsmethode für HHCRSP (LDIC 2014 Best Paper Award)

exakte Lösungsmethode für VRP für mobile P�egedienstebasiert auf Dekompositionsansatz von Benders (1962)

Master : Routing-SubproblemSlave : Scheduling-Subproblem

solve master → 𝑥∗

is slave feasible for 𝑥∗

optimal solution found

add combinatorial Benders‘ cut see Codato, Fischetti, 2006

𝑥𝑖𝑗𝑣𝑠∗

𝑖,𝑗,𝑣,𝑠∈𝑀𝐼𝑆:𝑥𝑖𝑗𝑣𝑠∗ =0

+ (1 − 𝑥𝑖𝑗𝑣𝑠∗ )

𝑖,𝑗,𝑣,𝑠∈𝑀𝐼𝑆:𝑥𝑖𝑗𝑣𝑠∗ =1

≥ 1

yes no

search for Minimal Infeasibility Set



Neue Schnittebene

solve master → 𝑥∗

is slave feasible for 𝑥∗

optimal solution found

search for Minimal Infeasibility Set

add combinatorial Benders‘ cut

𝑥𝑖𝑗𝑣𝑠𝑖,𝑗,𝑣,𝑠∈𝑀𝐼𝑆

≤ 𝑀𝐼𝑆 − 1

yes no

⇒ Für mittelgroÿe Instanzen: optimale Lösungen



Ortsungebundene Synchronisation (Typ III und IV)

Folgende Entscheidungen sind zu tre�en:

Welche Fahrzeuge fahren welche Kunden an?Wann kommen die Fahrzeuge bei den Kunden an?Synchronisationsfragen:

Ist Synchronisation erforderlich? (z. B. wegen mangelnder Infrastruktur oder nicht ausreichender Ladung)

Ist Synchronisation nützlich? (d. h. lohnt es sich zu synchronisieren?)

• Welche Fahrzeuge sollen sich treffen?• Wann sollen sich die Fahrzeuge treffen?

• Wo sollen sich die Fahrzeuge treffen?• Welche Rolle spielen die Fahrzeuge: empfangend oder abgebend?• Wie viele Ladungseinheiten sollen transferiert werden?

OR



Modell und Konstruktionsverfahren

tiv′ − tiv ≥ δmin

i −M · (4− αiv′ − ui −∑j∈C0

xijv −∑k∈C0

xikv′ ) ∀i ∈ S, v , v ′ ∈ V : v 6= v ′

tiv′ − tiv ≤ δmax

i + M · (4− αiv′ − ui −∑j∈C0

xijv −∑k∈C0

xikv′ ) ∀i ∈ S, v , v′ ∈ V : v 6= v ′

Start: • Kunden: aufsteigend sortiert nach 𝑙𝑖

• Fahrzeuge: aufsteigend sortiert nach 𝑐𝑣

und schnellster „Erreichbarkeit“ZF 𝑣 + +

𝑄 ≥ 𝑞𝑖

𝑖, 𝑣

𝑜𝑣𝑘 = 𝑖 𝑘 + + 𝑖 + +

Synch

𝐸𝐷, ∆, 𝑣′, ZF

𝑄𝑣′ + 𝑄𝑣 ≥ 𝐸𝐷 𝑜𝑣𝑘 = 𝑠; 𝑜𝑣′𝑘 = 𝑠; 𝑜𝑣𝑘 = 𝑖 𝑘 + 2; 𝑖 + +

𝑞𝑖 ≥ max𝑣∈𝑉

𝑄𝑣

Pflichtsynch.: 𝑄𝑣′ + 𝑄𝑣 ≥ 𝑞𝑖 𝑜𝑣𝑘 = 𝑠; 𝑜𝑣′𝑘 = 𝑠; 𝑜𝑣𝑘 = 𝑖 𝑘 + 2; 𝑖 + +

ja

ja

ja

ja nein

nein

nein

nein

𝑖 = |𝐶| STOP



Agenda







Zusammenfassung

1 Zeit-Raum-Klassi�kationsschema: systematische Erschlieÿung der Syn-chronisationstypen

ortsgebundene Synchronisation: zwingend nötig, Dienstleistungsbereichortsungebundene Synchronisation: optional, mit Kapazitäten

2 Für alle Typen wurden MILP Modelle entwickelt, die aufeinander aufbauen⇒ Modell für ortsungebundene Synchronisation ist generisch für alle Typen

3 weitere Lösungsmethoden:ortsgebundene Synchronisation:

Metaheuristik: AVNSExaktes Verfahren: Dekompositionsansatz nach Benders

ortsungebundene Synchronisation:Metaheuristik: in Arbeit



Ausblick

Dieses Projekt bietet einen Ausgangspunkt für die zukünftige Forschung, z. B.:1 Suche nach leistungsfähigeren Verfahren2 Einbeziehung der Arbeitszeiten der Fahrer3 Untersuchung der ökologischen Aspekte wie z. B. Reduktion der Treibhaus-

gasemissionen durch Konsolidierung der Waren im intermodalen Transport



Danke für Ihre Aufmerksamkeit!

mailto:[email protected]

http://prodlog.wiwi.uni-halle.de

Acknowledgments. Dieses Forschungsprojekt wurde von der Deutschen Forschungsgemeinschaft �nanziert(Projektnummer B02110263).



Balsliemke, F. (2004). Logistiksysteme zur integrierten Distribution undRedistribution: Eine ökonomische Analyse am Beispiel der deutschenMöbelbranche. Deutscher Universitäts-Verlag. Doctoral disseration,University of Paderborn.

Benders, J. F. (1962). Partitioning procedures for solvinb mixed-ivariablesprogramming problems. Numerische Mathematik, 4:238�252.

Bredström, D. and Rönnqvist, M. (2008). Combined vehicle routing andscheduling with temporal precedence and synchronization constraints.European Journal of Operational Research, 191:19�31.

Del Pia, A. and Filippi, C. (2006). A variable neighborhood descent algorithmfor a real waste collection problem with mobile depots. InternationalTransactions in Operational Research, 13(2):125�141.

Drexl, M. (2012). Synchronization in Vehicle Routing�A Survey of VRPs withMultiple Synchronization Constraints. Transportation Science, 46(3):297�316.

Eveborn, P., Flisberg, P., and Rönnqvist, M. (2006). LAPS CARE�anoperational system for sta� planning of home care. European Journal ofOperations Research, 171:962�976.

Flisberg, P., Forsberg, M., and Rönnqvist, M. (2007). Optimization basedplanning tools for routing of forwarders at harvest areas. Canadian Journal ofForest Research, 37:2153�2163.



Freling, R., Huisman, D., and Wagelmans, A. (2003). Models and algorithms forintegration of vehicle and crew scheduling. Journal of Scheduling, 6(1):63�85.

Goel, A. and Meisel, F. (2013). Workforce routing and scheduling for electricitynetwork maintenance with downtime minimization. European Journal ofOperational Research, 213(1):210�228.

Golden, B. L., Raghavan, S., and Wasil, E. A., editors (2008). The VehicleRouting Problem: Latest Advandes and New Challenges, volume 43 ofOperations Research/Computer Science Interfaces Series. Springer, New York.

Haase, K., Desaulniers, G., and Desrosiers, J. (2001). Simultaneous vehicle andcrew scheduling in urban mass transit systems. Transportation Science,35(3):286�303.

Hansen, P. and Mladenovi¢, N. (2001). Variable Neighborhood Search:Principles and applications. European Journal of Operational Research,130:449�467.

Hombrink, S. (2008). Das Problem der Tourenplanung mit einem mobilenDepot. Martin-Lither-University Halle-Wittenberg.

Kergosien, Y., Lenté, C., and Billaut, J.-C. (2009). Home Health Care Problem:An extended multiple Traveling Salesman Problem. In MultidisciplinaryInternational Conference on Scheduling: Theory and Applications (MISTA2009), pages 85�92.



Kunze, O., Baumgärtel, H., Neitmann, A., and Rosemeier, S. (2012). DynamicTruck Meeting (DTM). KIT Scienti�c Publishing, Karlsruhe.

Lee, Y. H., Jung, J. W., and Lee, K. M. (2006). Vehicle routing scheduling forcross-docking in the supply chain. Computers & Industrial Engineering,51(2):247�256.

Li, Y., Lim, A., and Rodrigues, B. (2005). Manpower allocation with timewindows and jobteaming constraints. Naval Research Logistics,52(4):302�311.

Mankowska, D. S. (2014). Synchronization in vehicle routing: Benders'decomposition for the home health care routing and scheduling problem. InKreowski, H.-J., Scholz-Reiter, B., and Thoben, K.-D., editors, Dynamic inLogistics, Fourth International Conference, LDIC 2014, Bremen, Germany,February 2014 Proceedings, Lecture Notes in Logistics. Springer.

Mankowska, D. S., Bierwirth, C., and Meisel, F. (2011). Modelling thesynchronization of transport means in logistics service operations. In Böse,J. W., Hu, H., Jahn, C., Shi, X., Stahlbock, R., and Voÿ, S., editors,Computational Logistics, volume 6971 of Lecture Notes in Computer Science,pages 74�85. Springer Berlin-Heidelberg.

Mankowska, D. S., Bierwirth, C., and Meisel, F. (2012a). Spatial and temporalsynchronization of mobile servers in service networks. In Klatte, D., Lüthi,



H.-J., and Schmedders, K., editors, Operations Reserach Proceedings 2011,pages 263�268. Springer Berlin-Heidelberg.

Mankowska, D. S., Bierwirth, C., and Meisel, F. (2012b). A vehicle routingproblem with cargo transfer options. In Günther, H.-O., Kim, K. H., andKopfer, H., editors, Proceedings of the 2012 International Conference onLogistics and Maritime Systems (LOGMS 2012), pages 417�427.

Mankowska, D. S., Meisel, F., and Bierwirth, C. (2014). The home health carerouting and scheduling problem with interdependent service. Health CareManagement Science, 17(1):15�30.

Meisel, F. and Kopfer, H. (2014). Synchronized routing of active and passivemeans of transport. OR Spectrum, 36:297�322.

Rasmussen, M. S., Justesen, T., Dohn, A., and Larsen, J. (2012). The HomeCare Crew Scheduling Problem: Preference-Based Visit Clustering andTemporal Dependencies. European Journal of Operational Research,219:598�610.

Repoussis, P. P. and Gounaris, C. E., editors (2013). Special Issue on VehicleRouting and Scheduling: Recent Trends and Advances, volume 7 ofOptimization Letters. Springer.

Toth, P. and Vigo, D., editors (2002). The Vehicle Routing Problem. SIAMDorota Sªawa Ma«kowska Tourenplanung mit Fahrzeugsynchronisation 28


monographs on discrete mathematics and applications. Society for Industrialand Applied Mathematics, Philadelphia.

Weise, T., Podlich, A., Reinhard, K., Gorldt, C., and Geihs, K. (2009).Evolutionary freight transportation planning. In Giacobini, M., Brabazon, A.,Cagnoni, S., Di Caro, G. A., adn A. I. Esperacia-Alcázar, A. E., Farooq, M.,Fink, A., and Machado, P., editors, Applications of Evolutionary Computing,volume 5484 of Lecture Notes in Computer Science, pages 768�777. SpringerBerlin-Heidelberg.

Wen, M., Larsen, J., Clausen, J., Cordeau, J.-F., and Laporte, G. (2009).Vehicle routing with cross-docking. Journal of the Operational ResearchSociety, 60:1708�1718.

Yu, W. and Egbelu, P. J. (2008). Scheduling of inbound and outbound trucks incross docking systems with temporary storage. European Journal ofOperational Research, 184:377�396.


Documents

Modelle und Methoden zur ourenplanungT mit