A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints

A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints

0.00 Avg rating0 Votes
Article ID: iaor19932214
Country: Germany
Volume: 14
Issue: 2
Start Page Number: 91
End Page Number: 106
Publication Date: Apr 1992
Journal: OR Spektrum
Authors: ,
Keywords: sets
Abstract:

In this paper the authors 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 time tstart 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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.