IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v44y1998i10p1447-1459.html
   My bibliography  Save this article

A Subpath Ejection Method for the Vehicle Routing Problem

Author

Listed:
  • César Rego

    (Faculdade de Ciências---Universidade de Lisboa, Departmento de Estatística e Investigação Operacional---DEIO, Campo Grande C/2, 1700 Lisboa, Portugal)

Abstract

Generically, ejection chains are methods conceived to allow solution transformations to be efficiently carried out by modifying a variable number of their components at each step of a local search algorithm. We consider a subpath ejection chain method for the vehicle routing problem (VRP) under capacity and route length restrictions. The method undertakes the identification of a substructure named the flower reference structure which, besides coordinating moves during an ejection chain construction, allows the creation of neighborhood structures with interesting combinatorial characteristics. Specifically, we base the method on a fundamental property of creating alternating paths and cycles during an ejection chain construction. A new algorithm based on a Tabu search framework is proposed, and computational results on a set of academic and real-world problems indicate that the algorithm may be a good alternative to the best heuristic algorithms for the VRP.

Suggested Citation

  • César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:10:p:1447-1459
    DOI: 10.1287/mnsc.44.10.1447
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.44.10.1447
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.44.10.1447?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    2. Stewart, William R. & Golden, Bruce L., 1984. "A Lagrangean relaxation heuristic for vehicle routing," European Journal of Operational Research, Elsevier, vol. 15(1), pages 84-88, January.
    3. Julien Bramel & David Simchi-Levi, 1995. "A Location Based Heuristic for General Routing Problems," Operations Research, INFORMS, vol. 43(4), pages 649-660, August.
    4. Rego, Cesar, 1998. "Relaxed tours and path ejections for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 522-538, April.
    5. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    6. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    7. Marshall L. Fisher, 1994. "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees," Operations Research, INFORMS, vol. 42(4), pages 626-642, August.
    8. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    9. B. Boffey & Francisco García & Gilbert Laporte & Juan Mesa & Blas Pelegrín, 1995. "Multiobjective routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 3(2), pages 167-220, December.
    10. Rego, Cesar & Roucairol, Catherine, 1995. "Using Tabu search for solving a dynamic multi-terminal truck dispatching problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 411-429, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ruiz, Ruben & Maroto, Concepcion & Alcaraz, Javier, 2004. "A decision support system for a real vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 153(3), pages 593-606, March.
    2. Zhang, Ying & Qi, Mingyao & Miao, Lixin & Liu, Erchao, 2014. "Hybrid metaheuristic solutions to inventory location routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 305-323.
    3. Martin-Iradi, Bernardo & Pacino, Dario & Ropke, Stefan, 2024. "An adaptive large neighborhood search heuristic for the multi-port continuous berth allocation problem," European Journal of Operational Research, Elsevier, vol. 316(1), pages 152-167.
    4. Colin Osterman & César Rego, 2016. "A k-level data structure for large-scale traveling salesman problems," Annals of Operations Research, Springer, vol. 244(2), pages 583-601, September.
    5. Szeto, W.Y. & Wu, Yongzhong & Ho, Sin C., 2011. "An artificial bee colony algorithm for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 126-135, November.
    6. César Rego & Fred Glover, 2010. "Ejection chain and filter-and-fan methods in combinatorial optimization," Annals of Operations Research, Springer, vol. 175(1), pages 77-105, March.
    7. Guido Perboli & Ferdinando Pezzella & Roberto Tadei, 2008. "EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(2), pages 361-382, October.
    8. Russell, Robert A. & Chiang, Wen-Chyuan, 2006. "Scatter search for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 169(2), pages 606-622, March.
    9. Edmund K. Burke & Timothy Curtois & Rong Qu & Greet Vanden Berghe, 2013. "A Time Predefined Variable Depth Search for Nurse Rostering," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 411-419, August.
    10. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    11. Braysy, Olli & Hasle, Geir & Dullaert, Wout, 2004. "A multi-start local search algorithm for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 159(3), pages 586-605, December.
    12. Rego, Cesar, 2001. "Technical note on the paper "An empirical study of a new metaheuristic for the traveling salesman problem" (by Shigeru Tsubakitani, James R. Evans, European Journal of Operational Research 1," European Journal of Operational Research, Elsevier, vol. 129(2), pages 456-459, March.
    13. Pacheco, J.A. & Delgado Serna, C.R., 2000. "Diseño de Metaheurísticos para Problemas de Rutas con Flota Heterogénea: Concentración Heurística," Estudios de Economia Aplicada, Estudios de Economia Aplicada, vol. 14, pages 137-151, Abril.
    14. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    2. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    3. N A Wassan, 2006. "A reactive tabu search for the vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(1), pages 111-116, January.
    4. Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    5. Crainic, Teodor Gabriel & Laporte, Gilbert, 1997. "Planning models for freight transportation," European Journal of Operational Research, Elsevier, vol. 97(3), pages 409-438, March.
    6. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    7. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    8. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    9. Sandra Zajac, 2018. "On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem," Journal of Heuristics, Springer, vol. 24(3), pages 515-550, June.
    10. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    11. Vigo, Daniele, 1996. "A heuristic algorithm for the asymmetric capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 89(1), pages 108-126, February.
    12. Sleman Saliba, 2006. "Heuristics for the lexicographic max-ordering vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(3), pages 313-336, September.
    13. Brandão, José, 2009. "A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 716-728, June.
    14. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    15. J Faulin & A García del Valle, 2008. "Solving the capacitated vehicle routing problem using the ALGELECT electrostatic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1685-1695, December.
    16. Gayialis, Sotiris P. & Tatsiopoulos, Ilias P., 2004. "Design of an IT-driven decision support system for vehicle routing and scheduling," European Journal of Operational Research, Elsevier, vol. 152(2), pages 382-398, January.
    17. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.
    18. Chiang, Wen-Chyuan & Russell, Robert A., 2004. "Integrating purchasing and routing in a propane gas supply chain," European Journal of Operational Research, Elsevier, vol. 154(3), pages 710-729, May.
    19. Lai, David S.W. & Caliskan Demirag, Ozgun & Leung, Janny M.Y., 2016. "A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 32-52.
    20. Brandao, Jose, 2004. "A tabu search algorithm for the open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 552-564, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:44:y:1998:i:10:p:1447-1459. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.