IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v211y2011i1p66-75.html
   My bibliography  Save this article

Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints

Author

Listed:
  • Felipe, Angel
  • Teresa Ortuño, M.
  • Tirado, Gregorio

Abstract

Logistics and transportation issues have been receiving increasing attention during the last decades and their requirements have gradually changed, making it necessary to take into account new situations and conditions. The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a pickup and delivery problem in which some additional precedence and loading constraints are imposed on the vehicle to be used. In this paper we approach the problem using intermediate infeasible solutions to diversify the search process and we develop some fixing procedures and infeasibility measures to deal with this kind of solutions and take advantage of their potential.

Suggested Citation

  • Felipe, Angel & Teresa Ortuño, M. & Tirado, Gregorio, 2011. "Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints," European Journal of Operational Research, Elsevier, vol. 211(1), pages 66-75, May.
    • Handle: RePEc:eee:ejores:v:211:y:2011:i:1:p:66-75
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00775-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. 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.
    3. Fuellerer, Guenther & Doerner, Karl F. & Hartl, Richard F. & Iori, Manuel, 2010. "Metaheuristics for vehicle routing problems with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 201(3), pages 751-759, March.
    4. A. Felipe & M. Ortuño & G. Tirado, 2009. "New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 190-213, July.
    5. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    6. Manuel Iori & Juan-José Salazar-González & Daniele Vigo, 2007. "An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints," Transportation Science, INFORMS, vol. 41(2), pages 253-264, May.
    7. Kimbrough, Steven Orla & Koehler, Gary J. & Lu, Ming & Wood, David Harlan, 2008. "On a Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch," European Journal of Operational Research, Elsevier, vol. 190(2), pages 310-327, October.
    8. Petersen, Hanne L. & Madsen, Oli B.G., 2009. "The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches," European Journal of Operational Research, Elsevier, vol. 198(1), pages 139-147, October.
    9. Michel Gendreau & Gilbert Laporte & René Séguin, 1996. "A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers," Operations Research, INFORMS, vol. 44(3), pages 469-477, June.
    10. Thomas Hanne, 2009. "On Utilizing Infeasibility in Multiobjective Evolutionary Algorithms," Lecture Notes in Economics and Mathematical Systems, in: Vincent Barichard & Matthias Ehrgott & Xavier Gandibleux & Vincent T'Kindt (ed.), Multiobjective Programming and Goal Programming, pages 113-122, Springer.
    11. Ejis, 2009. "Table of Contents," European Journal of Interdisciplinary Studies, Bucharest Economic Academy, issue 01, March.
    12. J-F Cordeau & M Gendreau & G Laporte & J-Y Potvin & F Semet, 2002. "A guide to vehicle routing heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 512-522, May.
    13. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    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. Manousakis, Eleftherios G. & Kasapidis, Grigoris A. & Kiranoudis, Chris T. & Zachariadis, Emmanouil E., 2022. "An infeasible space exploring matheuristic for the Production Routing Problem," European Journal of Operational Research, Elsevier, vol. 298(2), pages 478-495.
    2. Lars Magnus Hvattum & Gregorio Tirado & Ángel Felipe, 2020. "The Double Traveling Salesman Problem with Multiple Stacks and a Choice of Container Types," Mathematics, MDPI, vol. 8(6), pages 1-11, June.
    3. Hanne Pollaris & Kris Braekers & An Caris & Gerrit K. Janssens & Sabine Limbourg, 2016. "Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(2), pages 231-255, June.
    4. Cheang, Brenda & Gao, Xiang & Lim, Andrew & Qin, Hu & Zhu, Wenbin, 2012. "Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints," European Journal of Operational Research, Elsevier, vol. 223(1), pages 60-75.

    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. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    2. Manousakis, Eleftherios G. & Kasapidis, Grigoris A. & Kiranoudis, Chris T. & Zachariadis, Emmanouil E., 2022. "An infeasible space exploring matheuristic for the Production Routing Problem," European Journal of Operational Research, Elsevier, vol. 298(2), pages 478-495.
    3. Sumanta Basu & Ghosh, Diptesh, 2008. "A review of the Tabu Search Literature on Traveling Salesman Problems," IIMA Working Papers WP2008-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    4. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    5. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    6. 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.
    7. Lars Magnus Hvattum & Gregorio Tirado & Ángel Felipe, 2020. "The Double Traveling Salesman Problem with Multiple Stacks and a Choice of Container Types," Mathematics, MDPI, vol. 8(6), pages 1-11, June.
    8. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    9. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    10. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    11. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    12. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    13. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    14. 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.
    15. Michel Gendreau & Jean-Yves Potvin, 2005. "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 189-213, November.
    16. LECLUYSE, C. & VAN WOENSEL, Tom & PEREMANS, Herbert, 2007. "Vehicle routing with stochastic time-dependent travel times," Working Papers 2007018, University of Antwerp, Faculty of Business and Economics.
    17. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    18. Florent Hernandez & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A local branching matheuristic for the multi-vehicle routing problem with stochastic demands," Journal of Heuristics, Springer, vol. 25(2), pages 215-245, April.
    19. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    20. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.

    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:eee:ejores:v:211:y:2011:i:1:p:66-75. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.