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

The tree representation for the pickup and delivery traveling salesman problem with LIFO loading

Author

Listed:
  • Li, Yongquan
  • Lim, Andrew
  • Oon, Wee-Chong
  • Qin, Hu
  • Tu, Dejian

Abstract

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases.

Suggested Citation

  • Li, Yongquan & Lim, Andrew & Oon, Wee-Chong & Qin, Hu & Tu, Dejian, 2011. "The tree representation for the pickup and delivery traveling salesman problem with LIFO loading," European Journal of Operational Research, Elsevier, vol. 212(3), pages 482-496, August.
    • Handle: RePEc:eee:ejores:v:212:y:2011:i:3:p:482-496
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(11)00139-1
    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. Kalantari, Bahman & Hill, Arthur V. & Arora, Sant R., 1985. "An algorithm for the traveling salesman problem with pickup and delivery customers," European Journal of Operational Research, Elsevier, vol. 22(3), pages 377-386, December.
    2. Francesco Carrabs & Jean-François Cordeau & Gilbert Laporte, 2007. "Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 618-632, November.
    3. Matteo Fischetti & Paolo Toth, 1989. "An Additive Bounding Procedure for Combinatorial Optimization Problems," Operations Research, INFORMS, vol. 37(2), pages 319-328, April.
    4. Healy, Patrick & Moll, Robert, 1995. "A new extension of local search applied to the Dial-A-Ride Problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 83-104, May.
    5. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    6. 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.
    7. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    8. Manuel Iori & Silvano Martello, 2010. "Rejoinder on: 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 41-42, July.
    9. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    10. Li, Haibing & Lim, Andrew, 2003. "Local search with annealing-like restarts to solve the VRPTW," European Journal of Operational Research, Elsevier, vol. 150(1), pages 115-127, October.
    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. Bo Peng & Yuan Zhang & Yuvraj Gajpal & Xiding Chen, 2019. "A Memetic Algorithm for the Green Vehicle Routing Problem," Sustainability, MDPI, vol. 11(21), pages 1-20, October.
    2. Pereira, Armando Honorio & Mateus, Geraldo Robson & Urrutia, Sebastián Alberto, 2022. "Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks," European Journal of Operational Research, Elsevier, vol. 300(1), pages 207-220.
    3. Iassinovskaia, Galina & Limbourg, Sabine & Riane, Fouad, 2017. "The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 570-582.
    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.
    5. Huang, Baobin & Tang, Lixin & Baldacci, Roberto & Wang, Gongshu & Sun, Defeng, 2023. "A metaheuristic algorithm for a locomotive routing problem arising in the steel industry," European Journal of Operational Research, Elsevier, vol. 308(1), pages 385-399.
    6. Veenstra, Marjolein & Roodbergen, Kees Jan & Vis, Iris F.A. & Coelho, Leandro C., 2017. "The pickup and delivery traveling salesman problem with handling costs," European Journal of Operational Research, Elsevier, vol. 257(1), pages 118-132.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    6. Bortfeldt, Andreas & Hahn, Thomas & Männel, Dirk & Mönch, Lars, 2015. "Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 82-96.
    7. Francesco Carrabs & Jean-François Cordeau & Gilbert Laporte, 2007. "Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 618-632, November.
    8. Michel Gendreau & Jean-Yves Potvin, 2005. "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 189-213, November.
    9. Du, Jianhui & Zhang, Zhiqin & Wang, Xu & Lau, Hoong Chuin, 2023. "A hierarchical optimization approach for dynamic pickup and delivery problem with LIFO constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    10. Hu, Wuhua & Mao, Jianfeng & Wei, Keji, 2017. "Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system," European Journal of Operational Research, Elsevier, vol. 258(3), pages 943-957.
    11. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    12. Cordeau, Jean-François & Dell’Amico, Mauro & Falavigna, Simone & Iori, Manuel, 2015. "A rolling horizon algorithm for auto-carrier transportation," Transportation Research Part B: Methodological, Elsevier, vol. 76(C), pages 68-80.
    13. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    14. Manuel Ostermeier & Andreas Holzapfel & Heinrich Kuhn & Daniel Schubert, 2022. "Integrated zone picking and vehicle routing operations with restricted intermediate storage," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 795-832, September.
    15. Emmanouil E. Zachariadis & Christos D. Tarantilis & Chris T. Kiranoudis, 2017. "Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints," Operational Research, Springer, vol. 17(1), pages 115-143, April.
    16. Daniel Schubert & André Scholz & Gerhard Wäscher, 2017. "Integrated Order Picking and Vehicle Routing with Due Dates," FEMM Working Papers 170007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    17. Adejuyigbe O. Fajemisin & Steven D. Prestwich & Laura Climent, 2023. "Cutting uncertain stock and vehicle routing in a sustainability forestry harvesting problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(1), pages 139-164, April.
    18. Emmanouil E. Zachariadis & Christos D. Tarantilis & Chris T. Kiranoudis, 2012. "The Pallet-Packing Vehicle Routing Problem," Transportation Science, INFORMS, vol. 46(3), pages 341-358, August.
    19. Andrew Lim & Xingwen Zhang, 2007. "A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 443-457, August.
    20. Mauro Dell’Amico & Simone Falavigna & Manuel Iori, 2015. "Optimization of a Real-World Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 49(2), pages 402-419, May.

    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:212:y:2011:i:3:p:482-496. 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.