Acta Univ. Agric. Silvic. Mendelianae Brun. 2012, 60(7), 171-178 | DOI: 10.11118/actaun201260070171

Different versions of the savings method for the time limited vehicle routing problem

Petr Kučera
Katedra systémového inženýrství, Provozně ekonomická fakulta, Česká zemědělská univerzita v Praze, Kamýcká 129, 165 21 Praha 6-Suchdol, Česká republika

The time limited vehicle routing problem (TLVRP) stems from the vehicle routing problem. The main difference is that the routes are paths (not cycles), i.e. vehicles do not return to the central city (or at least we do not observe their way back). Costs are given for the straight routes between each pair of the cities and represent the time necessary for going through. Each path must not exceed a given time limit. The sum of times for all routes is to be minimized.
This problem is NP-hard. There are many various possibilities how to design the heuristics (approximation methods) to solve it. One of the ways of how to obtain an approximation method for the TLVRP is to modify the famous savings method by Clark and Wright (1964) for this purpose. In this paper we suggest several different versions of this method, test them in some instances, and evaluate and mutually compare the results of individual versions.

Keywords: time limited vehicle routing problem, vehicle routing problem, traveling salesman problem, savings method

Received: August 31, 2012; Published: July 2, 2013  Show citation

ACS AIP APA ASA Harvard Chicago IEEE ISO690 MLA NLM Turabian Vancouver
Kučera, P. (2012). Different versions of the savings method for the time limited vehicle routing problem. Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis, 60(7), 171-178. doi: 10.11118/actaun201260070171
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. BELFIORE, P. P., FAVERO, L. P. L., 2007: Scatter search for the fleet size and mix vehicle routing problem with time windows. Central Eur J Oper Res 15, 4: 351-368. DOI: 10.1007/s10100-007-0036-9 Go to original source...
    2. BLAZSIK, Z., IMREH, C., KOVACS, Z., 2008: Heuristic algorithms for a complex parallel machine scheduling problem. Central Eur J Oper Res 10: 63-211. Go to original source...
    3. BODIN, L., GOLDEN, B., ASSAD, A, BALL, M. O., 1983: Routing and scheduling of vehicles and crews: the state of art. Comput Oper Res 34, 10: 2918-2930.
    4. BORGULYA, I., 2008: An algorithm for the capacitated vehicle routing problem with route balancing. Central Eur J Oper Res 16, 4: 331-343. DOI: 10.1007/s10100-008-0062-2 Go to original source...
    5. BRANDÃO, J., 2004: A tabu search algorithm for the open vehicle routing problem. Eur J Oper Res 157, 3: 552-564. DOI: 10.1016/S0377-2217(03)00238-8 Go to original source...
    6. CHRISTOFIDES, N., 1976: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report CS-93-13, Carnegie Mellon University.
    7. CLARKE, G., WRIGHT, J. W., 1964: Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12: 568-581. DOI: 10.1287/opre.12.4.568 Go to original source...
    8. FU, Z., EGLESE, R., LI, L., 2005: A new tabu search heuristic for the open vehicle routing problem. J Oper Res Soc 56, 3: 267-274. DOI: 10.1057/palgrave.jors.2601817 Go to original source...
    9. HABR, J., 1964: Jednoduché optimalizační metody pro ekonomickou praxi. SNTL, Prague.
    10. KARP, R. M., 1979: A Patching algorithm for the non-symmetric traveling salesman problem, SIAM J of Comput 8: 561-573. DOI: 10.1137/0208045 Go to original source...
    11. KUČERA, P., HOUŠKA, M., BERÁNKOVÁ, M. H., 2008: Selected methods for the time limited vehicle routing problem. In: Proceedings of the 26th International Conference on Mathematical Methods in Economics 2008, Czech Society for Operations Research, Prague, pp. 303-307.
    12. KUČERA, P., JARKOVSKÁ, M., 2010: The optimization of pastry delivery for NOPEK bakery in Vysoké Mýto. Agris on-line 2, 4: 65-77.
    13. LAPORTE, G., 1992: Vehicle routing problem: an overview of exact and approximate algorithms. Eur J Oper Res 59, 3: 345-358. DOI: 10.1016/0377-2217(92)90192-C Go to original source...
    14. LENSTRA, J. K., RINNOOY KAN, A. H. G., 1981: Complexity of vehicle and scheduling problems. Networks 11, 2: 221-227. DOI: 10.1002/net.3230110211 Go to original source...
    15. LI, F., GOLDEN, B., WASIL, E., 2007: The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Comput Oper Res 34, 10: 2918-2930. DOI: 10.1016/j.cor.2005.11.018 Go to original source...
    16. LIN, S., KERNIGHAN, B. V., 1973: An effective heuristic algorithm for the traveling salesman problem. Oper Res, 21: 972-989. DOI: 10.1287/opre.21.2.498 Go to original source...
    17. MIRHASSANI, S. A., ABOLGHASEMI, N., 2011: A particle swarm optimization algorithm for open vehicle routing problem. Expert Syst Appl 38, 9: 11547-11551. DOI: 10.1016/j.eswa.2011.03.032 Go to original source...
    18. PELIKÁN, J., 2006: A time limited vehicle routing problem. Komunikacie 3: 9-11. Go to original source...
    19. PISINGER, D., ROPKE, S., 2007: A general heuristic for vehicle routing problems. Comput Oper Res 34, 8: 2403-2435. DOI: 10.1016/j.cor.2005.09.012 Go to original source...
    20. POLI, R., KENNEDY, J., BLACKWELL, T., 2007: Particle swarm optimization an overview. Swarm Intell 1: 33-57. DOI: 10.1007/s11721-007-0002-0 Go to original source...
    21. REPOUSSIS, P. P., TARANTILIS, C. D., BRÄYSY, O., IOANNOU, G., 2010: A hybrid evolution strategy for the open vehicle routing problem. Comput Oper Res 37, 3: 443-455. DOI: 10.1016/j.cor.2008.11.003 Go to original source...
    22. ROSENKRANTZ, D. J., STEARNS, R. E., LEWIS, P. M., 1977: An analysis of several heuristics for the traveling salesman problem. SIAM J of Comput 6: 563-581. DOI: 10.1137/0206041 Go to original source...
    23. SALARI, M., TOTH, P., TRAMONTANI, A., 2010: An ILP improvement procedure for the Open Vehicle Routing Problem. Comput Oper Res 37, 12: 2106-2120. DOI: 10.1016/j.cor.2010.02.010 Go to original source...
    24. TARANTILIS, C. D., IOANNOU, G., KIRANOUDIS, C. T., PRASTACOS, G. P., 2004: A threshold accepting approach to the open vehicle routing problem. RAIRO - Oper Res 38, 4: 345-360. DOI: 10.1051/ro:2004029 Go to original source...
    25. THANGIAH, S. R., FERGANY, A., AWAN, S., 2007: Real-time split-delivery pickup and delivery time window problems with transfers. Central Eur J Oper Res 15, 4: 329-349. DOI: 10.1007/s10100-007-0035-x Go to original source...
    26. VAN DER CRUYSSEN, P., RIJCKAERT, M., 1978: Heuristic for the asymmetric traveling salesman problem. J of Oper Res Soc 30: 697-701. DOI: 10.1057/jors.1978.147 Go to original source...
    27. WEBB, J., 1971: An effective heuristic algorithm for the traveling salesman problem. Oper Res 21: 498-516. Go to original source...
    28. YU, S., DING, C., ZHU, K., 2011: A hybrid GA-TS algorithm for open vehicle routing optimization of coal mines material. Expert Syst. Appl. 38, 8: 10568-10573. DOI: 10.1016/j.eswa.2011.02.108 Go to original source...
    29. ZACHARIADIS, E. E., KIRANOUDIS, C. T., 2009: An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Comput Oper Res 37, 4: 712-723. DOI: 10.1016/j.cor.2009.06.021 Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY NC ND 4.0), which permits non-comercial use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content