×

A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints. (English) Zbl 0757.90020

Summary: 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 weak, 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 \(t_{\text{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.

MSC:

90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ball MO, Derigs U, Hilbrand C, Metz A (1990) Matching problems with generalized upper bound side constraints. Networks 20:703–721 · Zbl 0716.90097 · doi:10.1002/net.3230200602
[2] Bertsekas DP, Tseng P (1988) The relax codes for linear minimum cost network flow problems. Ann Oper Res 7:125–190 · doi:10.1007/BF02288322
[3] Derigs U (1981) Engpass – Zielfunktion und Zeit/Kosten – Tradeoff beim Transportproblem. Doctoral Dissertation, University of Cologne
[4] Derigs U, Metz A (1990a) Matching problems with Knapsack side constraints. A computational study. Working paper · Zbl 0768.90061
[5] Derigs U, Metz A (1990b) On the matching-based approach for solving set partitioning problems. Working paper
[6] Fisher M (1987) System design for express airlines. Doctoral Dissertation, Massachusetts Institute of Technology
[7] Fisher ML (1981) The Lagrangean relaxation method for solving integer programming problems. Manag Sci 27:1–18 · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[8] Fisher ML, Kedia P (1990) Optimal solution of set covering/partitioning problems using dual heuristics. Manag Sci 36:674–688 · Zbl 0706.90048 · doi:10.1287/mnsc.36.6.674
[9] Glover F, Klingmann D, Karney D, Napier A (1974) A computational study on start procedures, basis changev criteria, and solution algorithms for transportation problems. Manag Sci 20:793–813 · Zbl 0303.90039 · doi:10.1287/mnsc.20.5.783
[10] Nemhauser GL, Weber G (1979) Optimal set partitioning, matching and lagrangean duality. Naval Res Logist Q 26:553–563 · Zbl 0496.90057
[11] Poljak BT (1967) A general method for solving extremum problems. Soviet Math Dokl 8:593–597 · Zbl 0177.15102
[12] Zowe J (1987) Optimization with nonsmooth data. OR Spektrum 9:195–205 · Zbl 0635.90077 · doi:10.1007/BF01719827
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.