[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Bent, R., van Hentenryck, P.: A two-stage hybrid local search for the vehicle routing problem with time windows. Transp. Sci. 38(4), 515–530 (2004)

    Article  Google Scholar 

  • Blum, C., Roli, A.: Metaheuristics in combinatorial optimisation: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Bräysy, O.: Local search and variable neighborhood search algorithms for the vehicle routing problem with time windows. Acta Wasaensia 87, University Wasaenis, Vaasa (2001)

  • Bräysy, O.: A reactive variable neighborhood search algorithm for the vehicle routing problem with time windows. INFORMS J. Comput. 15(4), 347–368 (2003)

    Article  MathSciNet  Google Scholar 

  • Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows part I: route construction and local search algorithms. Transp. Sci. 39(1), 104–118 (2005)

    Article  Google Scholar 

  • Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M., Soumis, F.: The vehicle routing problem with time windows. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, pp. 157–193. SIAM, Philadelphia (2002)

    Google Scholar 

  • Cordone, R., Calvo, R.W.: A heuristic for the vehicle routing with time windows. J. Heur. 7, 107–129 (2001)

    Article  MATH  Google Scholar 

  • Choi, E., Tcha, D.-W.: A column generation approach for the heterogeneous fleet vehicle routing problem. Comput. Oper. Res., doi:10.1016/j.cor.2005.08.002 (2005)

  • Clarke, G., Wright, J.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)

    Article  Google Scholar 

  • Desrochers, M., Verhoog, T.W.: A new heuristic for the fleet size and mix vehicle routing problem. Comput. Oper. Res. 18(3), 263–274 (1991)

    Article  MATH  Google Scholar 

  • Dell-Amico, M., Monaci, M., Pagani, C., Vigo, D.: Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Technical Report, Observatorio Logistico, Università di Modena e Reggio Emilia, Italy (2006)

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

    Article  MATH  Google Scholar 

  • García-López, F., Melián-Batista, B., Moreno-Pérez, J.A., Moreno-Vega, J.M.: The parallel variable neighborhood search for the p-median problem. J. Heur. 8, 375–388 (2002)

    Article  MATH  Google Scholar 

  • Gendreau, M., Potvin, J.Y.: Metaheuristics in combinatorial optimization. Ann. Oper. Res. 140, 189–213 (2005)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

  • Geysens, F., Golden, B., Assad, A.: A new heuristic for determining fleet size composition. Math. Program. Stud. 26, 233–236 (1986)

    Google Scholar 

  • Glover, F.: New ejection chain and alternating path methods for travelling salesman problem. In: Balci, O., Sharda, R., Zenios, S. (eds.) Computer Science and Operation Research: New Development in Their Interfaces, pp. 449–509. Pergamon Press, Oxford (1992)

    Google Scholar 

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

    Article  MATH  Google Scholar 

  • Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)

    Article  MATH  Google Scholar 

  • Ioannou, G., Kritikos, M., Prastacos, G.: A greedy look-ahead heuristic for the vehicle routing problem with time windows. J. Oper. Res. Soc. 52, 523–537 (2001)

    Article  MATH  Google Scholar 

  • Kindervater, G.A.P., Savelsbergh, M.W.P.: Vehicle routing: handling edge exchanges. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. pp. 337–360. Wiley, UK (1998)

    Google Scholar 

  • Li, F., Golden, B., Wasil, E.: A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Comput. Oper. Res., doi:10.1016/j.cor.2005.10.015 (2006)

  • Liu, F.H., Shen, S.Y.: A method for vehicle routing problem with multiple vehicle types and times windows. Proc. Nat. Sci. Counc. Part A Phys. Sci. Eng. 23(4), 526–536 (1999a)

    Google Scholar 

  • Liu, F.H., Shen, S.Y.: The fleet size and mix routing problem with time windows. J. Oper. Res. Soc. 50(7), 721–732 (1999b)

    Article  MATH  Google Scholar 

  • 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. pp. 131–153. Wiley, New York (1996)

    Google Scholar 

  • Polacek, M., Hartl, R.F., Doerner, K.: A variable neighborhood search for the multi depot vehicle routing problem with time windows. J. Heur. 10, 613–627 (2004)

    Article  Google Scholar 

  • Renaud, J., Boctor, F.F.: A sweep-based algorithm for the fleet size and mix vehicle routing problem. Eur. J. Oper. Res. 140, 618–628 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  • Rochat, Y., Semet, F.: A tabu search approach for delivering pet food and flour in Switzerland. J. Oper. Res. Soc. 45, 1233–1246 (1994)

    Article  MATH  Google Scholar 

  • Rouseau, L.M., Gendreau, M., Pesant, G.: Using constraint based operators to solve the vehicle routing problem with time windows. J. Heur. 8, 43–58 (2002)

    Article  Google Scholar 

  • Salhi, S., Rand, G.: Incorporating vehicle routing into the vehicle fleet composition problem. Eur. J. Oper. Res. 66, 313–330 (1993)

    Article  MATH  Google Scholar 

  • Salhi, S., Sari, M., Touati, N.: Adaptation of some vehicle fleet mix heuristics. OMEGA 20, 653–660 (1992)

    Article  Google Scholar 

  • Semet, F.: A two-phase algorithm for the partial accessibility constrained vehicle routing. Ann. Oper. Res. 61, 45–65 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  • Semet, F., Taillard, E.D.: Solving real-life vehicle routing problems efficiently using tabu search. Ann. Oper. Res. 41, 469–488 (1993)

    Article  Google Scholar 

  • Solomon, M.M.: Algorithms for the vehicle routing and scheduling with time windows constraints. Oper. Res. 35, 254–265 (1987)

    MATH  MathSciNet  Google Scholar 

  • Taillard, E.D.: A heuristic column generation method for the heterogeneous fleet VRP. RAIRO 33, 1–14 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  • Tarantilis, C.D.: Solving the vehicle routing problem with adaptive memory programming methodology. Comput. Oper. Res. 32, 2309–2327 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  • Tarantilis, C.D., Kiranoudis, C.T.: BoneRoute: an adaptive memory-based method for effective fleet management. Ann. Oper. Res. 115, 227–241 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  • Tarantilis, C.D., Kiranoudis, C.T.: A flexible adaptive memory-based algorithm for real-life transportation operations: two case studies from dairy and construction sector. Eur. J. Oper. Res., doi:10.1016/j.ejor.2005.03.059 (2005)

  • Tarantilis, C.D., Kiranoudis, C.T., Vassiliadis, V.S.: A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. J. Oper. Res. Soc. 54, 65–71 (2003)

    Article  MATH  Google Scholar 

  • Tarantilis, C.D., Kiranoudis, C.T., Vassiliadis, V.S.: A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Eur. J. Oper. Res. 152, 148–158 (2004)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Management Science Laboratory, Department of Management Science & Technology, Athens University of Economics & Business, 28 Hydras st., 11362, Athens, Greece

    D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou & G. P. Prastacos

Authors
  1. D. C. Paraskevopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. P. Repoussis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. D. Tarantilis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. G. Ioannou
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. G. P. Prastacos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C. D. Tarantilis.

Additional information

This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Paraskevopoulos, D.C., Repoussis, P.P., Tarantilis, C.D. et al. A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows. J Heuristics 14, 425–455 (2008). https://doi.org/10.1007/s10732-007-9045-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-007-9045-z

Keywords

Search

Navigation