ISSN:
1436-6304
Keywords:
Vehicle routing with time-constraints
;
set partitioning
;
matching
;
relaxation
;
Vehicle Routing mit Zeitfenster-Bedingung
;
Set-Partitioning
;
Matching
;
Relaxation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Wir betrachten in dieser Arbeit ein spezielles Vehicle Routing Problem mit Zeitfenster-Restriktionen. Die Fahrzeuge einer nicht homogenen Flotte müssen während der ersten Hälfte einer Zeitperiode eine vorgegebene Anzahl von Kunden mit einer bestimmten Menge eines Gutes beliefern. Dabei ist für jeden Kunden ein spezifischer spätester Belieferungszeitpunkt vorgegeben. In der zweiten Hälfte der Zeitperiode müssen die Fahrzeuge jeweils eine bestimmte Menge eines Gutes von den Kunden zum Depot zurücktransportieren. Dabei ist hier nun für jeden Kunden ein spezifischer frühester Entsorgungszeitpunkt vorgegeben. Wir zeigen eine Formulierung dieses Problems als Set-Partitioning-Problem mit zwei zusätzlichen Klassen von Nebenbedingungen. Unter der Annahme, daß die Anzahl der Kunden, die jeweils von einem einzigen Fahrzeug beliefert bzw. entsorgt werden können, höchstens zwei beträgt, stellt sich dieses Problem als Matching-Problem mit Nebenbedingungen dar. Wir zeigen, wie durch Relaxation und die Anwendung effektiver Subgradiententechniken und effizienter Matching Algorithmen in akzeptabler Zeit gute approximative Lösungen bestimmt werden können.
Notes:
Summary In this paper we deal with the following special vehicle routing problem with time window constraints: Given a non-homogeneous fleet of vehicles and a fixed set of customers, during one time period, i.e. a day or a week, these customers have to be delivered in the “first half” of the period with a certain amount of goods. Thereby delivery may start at timet start say at the depot and for every customer there is a so-called cut-off-time for the latest possible delivery. In addition to travel time there is a certain delivery-time associated with every customer. In the “second half” of the time period the vehicles have to pick-up certain amounts of goods and to ship them to the depot. Again there is a cut-off time for the earliest possible pick-up and a certain time-span consumed for every pick-up. We show how this problem can be formulated as a (highdimensional) set partitioning problem with two additional nontrivial sets of side-constraints. Assuming that the number of customers that can be served by a single vehicle on a delivery or pick-up-pass is at most two, the problem reduces to a matching problem with side-constraints. Although the problem is still NP-complete it becomes practicable in the sense that by relaxation and applying effective optimization techniques from non-smooth optimization and efficient matching software good approximate solutions are constructed in acceptable time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01720353
Permalink
