Skip to main content
SpringerLink
Log in

A heuristic for vehicle fleet mix problem using tabu search and set partitioning

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

The vehicle fleet mix problem is a special case of the vehicle routing problem where customers are served by a heterogeneous fleet of vehicles with various capacities. An efficient heuristic for determining the composition of a vehicle fleet and travelling routes was developed using tabu search and by solving set partitioning problems. Two kinds of problems have appeared in the literature, concerning fixed cost and variable cost, and these were tested for evaluation. Initial solutions were found using the modified sweeping method. Whenever a new solution in an iteration of the tabu search was obtained, optimal vehicle allocation was performed for the set of routes, which are constructed from the current solution by making a giant tour. Experiments were performed for the benchmark problems that appeared in the literature and new best-known solutions were found.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Balinski ML and Quandt RE (1964). On an integer program for a delivery problem. Opns Res 12: 300–304.

    Article  Google Scholar 

  • Bolduc MC, Renaud J and Montreuil B (2006). Synchronized routing of seasonal products through a production/distribution network. Central Eur J Opl Res 14: 209–228.

    Article  Google Scholar 

  • Brandão J and Mercer A (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. Eur J Opl Res 100: 180–191.

    Article  Google Scholar 

  • Calvete HI, Galé C, Oliveros MJ and Sánchez-Valverde B (2005). A goal programming approach to vehicle routing problems with soft time windows. Eur J Opl Res 177: 1720–1733.

    Article  Google Scholar 

  • Choi E and Tcha DW (2005). A column generation approach to the heterogeneous fleet vehicle routing problem. Comput Opns Res 34: 2080–2095.

    Article  Google Scholar 

  • Dantzig G and Ramser J (1959). The truck dispatching problem. Mngt Sci 6: 80–91.

    Article  Google Scholar 

  • Dondo R and Cerdá J (2006). A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. Eur J Opl Res 176: 1478–1507.

    Article  Google Scholar 

  • Dullaert W, Janssens GK, Sorensen K and Vernimmen B (2002). New heuristics for the fleet size and mix vehicle routing problem with time windows. J Opl Res Soc 53: 1232–1238.

    Article  Google Scholar 

  • Gendreau M, Laporte G, Musaraganyi C and Taillard ED (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput Opns Res 26: 1153–1173.

    Article  Google Scholar 

  • Gheysens F, Golden B and Assad A (1984). A comparison of techniques for solving the fleet size and mix vehicle routing problem. Opns Res Spectrum 6: 207–216.

    Article  Google Scholar 

  • Gheysens FG, Golden B and Assad A (1986). A new heuristic for determining fleet size and composition. Math Programm Studies 26: 233–236.

    Article  Google Scholar 

  • Gillett B and Miller L (1974). A heuristic algorithm for the vehicle dispatch problem. Opns Res 22: 340–349.

    Article  Google Scholar 

  • Golden B, Assad A, Levy L and Gheysens FG (1984). The fleet size and mix vehicle routing problem. Comput Opns Res 11: 49–66.

    Article  Google Scholar 

  • Grabowski J and Pempera J (2005). Some local search algorithms for no-wait flow-shop problem with makespan criterion. Comput Opns Res 32: 2197–2212.

    Article  Google Scholar 

  • Irnich S (2000). A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles. Eur J Opl Res 122: 310–328.

    Article  Google Scholar 

  • Lima CMRR, Goldbarg MC and Goldbarg EFG (2004). A memetic algorithm for the heterogeneous fleet vehicle routing problem. Electronic Notes Discrete Math 18: 171–176.

    Article  Google Scholar 

  • Liu FH and Shen SY (1999). The fleet size and mix vehicle routing problem with time windows. J Opl Res Soc 50: 721–732.

    Article  Google Scholar 

  • Prins C (2002). Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case. J Math Modell Algorithms 1: 135–150.

    Article  Google Scholar 

  • Privé J, Renaud J, Boctor F and Laporte G (2006). Solving a vehicle routing problem arising in soft drink distribution. J Opl Res Soc 57: 1045–1052.

    Article  Google Scholar 

  • Taillard ED (1999). A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Opns Res 33: 1–14.

    Article  Google Scholar 

  • Tarantilis CD and Kiranoudis CT (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. J Food Eng 50: 1–9.

    Article  Google Scholar 

  • Tarantilis CD and Kiranoudis CT (2005). A flexible adaptive memory-based algorithm for real-life transportation operations: two case studies from dairy and construction sector. Eur J Opl Res 179: 806–822.

  • Tavakkoli-Moghaddam R, Safaei N and Gholipour Y (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Appl Math Comput 176: 445–454.

    Google Scholar 

  • Wassan NA and Osman IH (2002). Tabu search variants for the mix fleet vehicle routing problem. J Opl Res Soc 53: 768–782.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Yonsei University, Seoul, Korea

    Y H Lee, J I Kim, K H Kang & K H Kim

Authors
  1. Y H Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J I Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. K H Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. K H Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Y H Lee.

Appendix

Appendix

We introduce the new best solution for instances.

Instance 17 of VFMFC Table A1

Table 6 Table a1
Full size table

Instance 20 of VFMFC Table A2

Table 7 Table a2
Full size table

Instance 18 of VFMVC Table A3

Table 8 Table a3
Full size table

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lee, Y., Kim, J., Kang, K. et al. A heuristic for vehicle fleet mix problem using tabu search and set partitioning. J Oper Res Soc 59, 833–841 (2008). https://doi.org/10.1057/palgrave.jors.2602421

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2602421

Keywords

Search

Navigation