×
Chan, Yupo; Baker, S. F.

The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations. (English) Zbl 1082.90058

Math. Comput. Modelling 41, No. 8-9, 1035-1053 (2005).
Summary: At the core of many delivery-logistics problems is the multiple depot, multiple traveling salesmen facility-location problem (MDMTSFLP). This paper addresses a mixed integer MDMTSFLP formulation, expanded to include vehicle range and multiple service-frequency requirements. Here, vehicle range can be interpreted as limitation on tour length, often due to crew duty day restriction. Once defined, we use this optimization formulation to validate a heuristic solution for location and routing. Our heuristic employs a combination of the minimum spanning forest (MSF) and a modified Clarke-Wright (CW) procedure. The spanning forest is used for geographic partitioning and for depot location, while the CW routes the multiple aircraft fleets. Generalizing from a minimum \(K\)-tree, the MSF is an exact \(O(|I|^3)\) method for partitioning the demands into service regions and in locating regional depots, where \(|I|\) is the number of nodes.
The Defense Courier Service (DCS) aerial network provides a huge instance of the hierarchical multiple-frequency, range-restricted MDMTSFLP. For this network, we find our MSF/CW procedure to be suboptimal by 3.86 percent on average over 16 validation runs, with no run worse than 20.27 percent. We show that several depots of the DCS may be closed without a large increase of routing cost. The model and solution procedure presented here have implications upon many other logistics problems, which are typically characterized by multiple vehicular visits and shortage of crew duty days.

Cited in 9 Documents

MSC:

90B85 Continuous location
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
90B06 Transportation, logistics and supply chain management

Keywords:

Combined facility location and routing; Minimum K-tree; Multiple traveling salesmen; Multiple service frequency; Split delivery; Minimum spanning forest; Clarke-Wright heuristic

Software:

VRP; AMPL
PDF BibTeX XML Cite
\textit{Y. Chan} and \textit{S. F. Baker}, Math. Comput. Modelling 41, No. 8--9, 1035--1053 (2005; Zbl 1082.90058)
Full Text: DOI

References:

[1] Barnhart, C.; Schneur, R. R., Air network design for express shipment service, 44, 6, 852-863 (1996) · Zbl 0879.90077
[2] Bruns, A., Restructuring of Swiss parcel delivery services, OR Spektrum, 22, 2, 285-302 (2000) · Zbl 0970.90044
[3] Hall, R. W., Pickup and delivery systems for overnight carriers, Transportation Research, 30A, 3, 173-187 (1996)
[4] Achutan, N. R.; Caccetta, L.; Hill, S., A new sub-tour elimination constraint for the vehicle routing problem, European Journal of Operational Research, 91, 573-586 (1996) · Zbl 0924.90057
[5] Kulkarni, R. V.; Bhave, P. R., Integer programming formulations of vehicle routing problems, European Journal of Operational Research, 20, 58-67 (1985)
[6] Brodie, G. R.; Waters, C. D., Integer linear programming formulation for vehicle routing problems, European Journal of Operational Research, 34, 403-404 (1988) · Zbl 0825.90354
[7] Dror, M.; Trudeau, P., Savings by split delivery routing, Transportation Science, 23, 141-145 (1989) · Zbl 0668.90044
[8] Lee, C.-C.; Epelman, M.; White, C. C.; Bozer, Y. A., A Shortest Path Approach to the Multiple-Vehicle Routing Problem (2001), Department of Industrial and Operations Engineering, University of Michigan: Department of Industrial and Operations Engineering, University of Michigan New York
[9] Golden, B. L.; Laporte, G.; Taillard, E. D., An adaptive memory heuristic for a class of vehicle routing problems with minmax objective, Computers & Operations Research, 24, 5, 445-452 (1997) · Zbl 0882.90031
[10] Bertsimas, D. J., Traveling salesman facility location problems, Transportation Science, 23, 3, 184-191 (1989) · Zbl 0682.90039
[11] Laporte, G., An exact algorithm for solving a capacitated location-routing problem, Annals of Operations Research, 6, 293-310 (1986)
[12] Laporte, G., The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358 (1992) · Zbl 0761.90034
[13] Kim, D.; Barnhart, C.; Ware, K.; Reinhardt, G., Multimodal express package delivery: A service network design application, Transportation Science, 33, 4, 391-407 (1999) · Zbl 0958.90004
[14] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964)
[15] Beltrami, E. J.; Bodin, L. D., Networks and vehicle routing for municipal waste collection, (Boesch, F. T., Large-Scale Networks: Theory and Design (1976), IEEE Press: IEEE Press Ann Arbor, MI) · Zbl 0284.90032
[16] Golden, B. L., Implementing vehicle routing algorithms, Networks, 7, 113-148 (1977) · Zbl 0359.90054
[17] Naddef, D., A remark on ‘integer linear programming formulation for a vehicle routing problem’ by N.R. Achutan and L. Caccetta, or how to use the Clarke and Wright savings to write such integer linear programming formulations, European Journal of Operational Research, 75, 238-241 (1994) · Zbl 0811.90030
[18] Syslo, M. M., Discrete Optimization Algorithms with PASCAL Programming (1983), Prentice Hall: Prentice Hall New York · Zbl 0574.90057
[19] Held, M.; Karp, R. M., The traveling-salesman problem and minimum spanning trees: Part II, Mathematical Programming, 1, 6-25 (1971) · Zbl 0232.90038
[20] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley-Interscience: Wiley-Interscience Englewood Cliffs, NJ · Zbl 0469.90052
[21] Fisher, M. L., Optimal solution of vehicle routing problems using minimum \(K\)-trees, Operations Research, 42, 626-642 (1994) · Zbl 0815.90066
[22] Fisher, M. L., A polynomial algorithm for the degree-constrained minimum \(K\)-tree problem, Operations Research, 42, 775-779 (1994) · Zbl 0815.90131
[23] Achutan, N. R.; Caccetta, L., Integer linear programming formulation for a vehicle routing problem, European Journal of Operational Research, 52, 86-89 (1991) · Zbl 0727.90059
[24] Derochers, M.; Laport, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Operations Research Letters, 10, 27-36 (1991) · Zbl 0723.90081
[25] Baker, E., An exact algorithm for the time-constrained traveling salesman problem, Operations Research, 31, 5, 938-945 (1983) · Zbl 0549.90072
[26] Glover, F.; Klingman, D., Note on admissible exchanges in spanning trees, Advances in Management Studies, 3.2, 101-104 (1984)
[27] Chan, Y.; Carter, W. B.; Burnes, M., A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, Computers & Operations Research, 28, 803-826 (2001) · Zbl 1027.90034
[28] Mandl, C., Applied Network Optimization (1979), Academic Press: Academic Press New York · Zbl 0426.90053
[29] Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M., Approximate algorithms for the traveling salesman problem, (Proc. 15th Ann. IEEE Symp. on Switching and Automata Theory (1974)), 33-42
[30] Gillett, B.; Miller, L., A heuristic algorithm for the vehicle dispatch problem, Operations Research, 22, 340-349 (1974) · Zbl 0274.90013
[31] Fisher, M. L.; Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11, 109-124 (1981)
[32] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (1993), Scientific Press: Scientific Press New York
[33] Wu, T.-H.; Low, C.; Bai, J.-W., Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29, 1393-1415 (2002) · Zbl 0994.90019
[34] Chan, Y.; Merrill, D., A probabilistic multiple-traveling-salesman-facility-location problem: asymptotic analysis using space-filling curve heuristic, Military Operations Research, 3, 2, 37-53 (1997)
[35] Bramel, J.; Simchi-Levi, D., The Logic of Logistics (1997), Springer-Verlag · Zbl 0931.90002
[36] Chan, L. M.A.; Simchi-Levi, D., Probabilistic analyses and practical algorithms for multi-echelon distribution systems (1994), Department of Industrial Engineering and Operations Research, Columbia University: Department of Industrial Engineering and Operations Research, Columbia University New York
[37] Chan, L. M.A.; Federgruen, A.; Simchi-Levi, D., Probabilistic analyses and practical algorithms for inventory routing models, Operations Research, 46, 1, 96-106 (1998) · Zbl 0996.90007
[38] Gendreau, M.; Laporte, G.; Potvin, G., Vehicle Routing: Modern Heuristics (1997), Wiley: Wiley New York · Zbl 0899.90083
[39] Anily, S.; Federgruen, A., Structured partitioning problems, Operations Research, 39, 130-149 (1991) · Zbl 0747.90080
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.