Communications - Scientific Letters of the University of Zilina 2013, 15(1):6-13 | DOI: 10.26552/com.C.2013.1.6-13

The Shrinking and Expanding Heuristic for the Fleet Size and Mix Vehicle Routing Problem

Urooj Pasha1, Arild Hoff1, Arne Lokketangen1
1 Molde University College, Specialized University in Logistics, Molde, Norway

The FSMVRP (Fleet Size and Mix Vehicle Routing Problem) is a variant of the classical Capacitated Vehicle Routing Problem, CVRP. We suggest a new methodology, called the Shrinking and Expanding Heuristic (SEH) which is incorporated in a standard tabu search. To determine an appropriate fleet mix is a major challenge in this type of problem and the SEH technique is especially developed to find a good combination of vehicles by introducing a mechanism for changing the existing fleet mix during the search, thus also changing the underlying route structure. The SEH utilizes the concept of depletion and expansion of routes depending upon the filling degree of a vehicle. This strategy is tested on standard problem instances and good quality solutions are obtained.

Keywords: shrinking and expanding heuristics, filling degree, fleet size and mix vehicle routing problem, tabu search

Published: March 31, 2013  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Pasha, U., Hoff, A., & Lokketangen, A. (2013). The Shrinking and Expanding Heuristic for the Fleet Size and Mix Vehicle Routing Problem. Communications - Scientific Letters of the University of Zilina, 15(1), 6-13. doi: 10.26552/com.C.2013.1.6-13
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. HOFF, A., ANDERSSON, H., CHRISTIANSEN, M., HASLE, G., LOKKETANGEN, A.: Industrial Aspects and Literature Survey: Fleet Composition and Routing. Computers & Operations Research 37, 2010, pp. 2041-2061. Go to original source...
    2. GOLDEN, B., ASSAD, A., LEVY, L., GHEYSENS, F.: The Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research 11, 1984, pp. 49-66. Go to original source...
    3. CLARKE, G., WRIGHT, J. V.: Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research 12, 1964, pp. 568-581. Go to original source...
    4. FISHER, M. L., JAIKUMAR, R.: A Generalized Assignment Heuristic for Vehicle Routing. Networks 11, 1981, pp. 109-124. Go to original source...
    5. GHEYSENS, F., GOLDEN, B., ASSAD, A.: A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem. Computers & Operations research 11 (1), 1986, pp.49-66. Go to original source...
    6. SALHI, S., RAND, G. K.: Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem. European J. of Operations Research 66, 1993, pp. 313-330. Go to original source...
    7. OSMAN, I., SALHI, S.: Local Search Strategies for the Vehicle Fleet Mix Problem. In: RAYWARD-SMITH, V. J., OSMAN, I. H., REEVES, C. R., SMITH, G. D. (Eds), Modern Heuristic Search Methods. Wiley : New York, 1996, pp.131-153.
    8. GENDREAU, M., LAPORTE, G., MUSARAGANYI, C., TAILLARD, E. D.: A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem. Computers & Operations Research 26, 1999, pp. 1153-1173. Go to original source...
    9. BRANDAO, J.: A Deterministic Tabu Search Algorithm for the Fleet Size and Mix Vehicle Routing Problem. European J. of Operational Research 195, 2009, pp. 716-728. Go to original source...
    10. GENDREAU, M., HERTZ, A., LAPORTE, G.: New Insertion and Post-Optimization Procedures for the Traveling Salesman Problem. Operations Research 40 (6), 1992, pp. 1086-1094. Go to original source...
    11. SUBRAMANIAN, A., PENNA, P. H. V., UCHOA, E., OCHI, L. S.: A Hybrid Algorithm for the Heterogeneous Fleet Vehicle Routing Problem. European J. of operational research 221, 2012, pp. 285-295. Go to original source...
    12. LOURENCO, H. R., MARTIN, O., STUTZLE, T.: Iterated Local Search. In GLOVER, F., KOCHENBERGER, G., (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, 2003, pp. 321-353. Go to original source...
    13. GLOVER, F., LAGUNA, M.: Tabu Search. Kluwer Academic Publishers, 1997. Go to original source...
    14. PASHA, U.: A Tabu Search Heuristic for Solving the Fleet Size and Mix Vehicle Routing Problem. Master thesis, Molde University College : Molde, 2008.
    15. FLOOD M. M.: The Traveling Salesman Problem. Operations Research 4, 1956, pp. 61-75. Go to original source...
    16. GENDREAU, M., HERTZ, A., LAPORTE, G.: A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science 40, 1994, pp. 1276-1290. Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits 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