Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 14 (1992), S. 91-106 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...