IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v38y2004i4p434-446.html
   My bibliography  Save this article

Dispatching of an Electric Monorail System: Applying Metaheuristics to an Online Pickup and Delivery Problem

Author

Listed:
  • Kai Gutenschwager

    (SimPlan AG, Off. Braunschweig, Adolfstraße 21, D-38102 Braunschweig, Germany)

  • Christian Niklaus

    (Institut für Wirtschaftswissenschaften, University of Technology Braunschweig, Abt-Jerusalem-Straße 7, D-38106 Braunschweig, Germany)

  • Stefan Voß

    (Institut für Wirtschaftsinformatik, University of Hamburg, Von-Melle-Park 5, D-20146 Hamburg, Germany)

Abstract

In this article we present a new solution approach for a specific online pickup and delivery problem as it occurs in a real-world dispatching task of electric monorail load carriers. The presented optimization module adapts the communication structure of the respective IT components of the warehouse system to facilitate an easy integration. Numerical results are presented comparing steepest descent as well as reactive tabu search and simulated annealing with the dispatching system used so far. Tests are performed on the basis of a detailed simulation model of the entire warehouse and show a clear superiority for this approach.

Suggested Citation

  • Kai Gutenschwager & Christian Niklaus & Stefan Voß, 2004. "Dispatching of an Electric Monorail System: Applying Metaheuristics to an Online Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 434-446, November.
    • Handle: RePEc:inm:ortrsc:v:38:y:2004:i:4:p:434-446
    DOI: 10.1287/trsc.1030.0066
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1030.0066
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1030.0066?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. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2000. "Diversion Issues in Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 34(4), pages 426-438, November.
    3. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    4. Harilaos N. Psaraftis, 1983. "An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows," Transportation Science, INFORMS, vol. 17(3), pages 351-357, August.
    5. Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    6. Bruce Hajek, 1988. "Cooling Schedules for Optimal Annealing," Mathematics of Operations Research, INFORMS, vol. 13(2), pages 311-329, May.
    7. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1991. "Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning," Operations Research, INFORMS, vol. 39(3), pages 378-406, June.
    8. Desrochers, M. & Lenstra, J. K. & Savelsbergh, M. W. P., 1990. "A classification scheme for vehicle routing and scheduling problems," European Journal of Operational Research, Elsevier, vol. 46(3), pages 322-332, June.
    9. Eglese, R. W., 1990. "Simulated annealing: A tool for operational research," European Journal of Operational Research, Elsevier, vol. 46(3), pages 271-281, June.
    10. Marshall L. Fisher & Kurt O. Jörnsten & Oli B. G. Madsen, 1997. "Vehicle Routing with Time Windows: Two Optimization Algorithms," Operations Research, INFORMS, vol. 45(3), pages 488-492, June.
    11. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1989. "Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning," Operations Research, INFORMS, vol. 37(6), pages 865-892, December.
    12. Norbert Ascheuer & Martin Grötschel & Atef Abdel-Aziz Abdel-Hamid, 1999. "Order picking in an automatic warehouse: Solving online asymmetric TSPs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(3), pages 501-515, July.
    13. 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.
    14. A Larsen & O Madsen & M Solomon, 2002. "Partially dynamic vehicle routing—models and algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(6), pages 637-646, June.
    15. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    16. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    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. 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.
    2. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    3. 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.
    4. Shaza Hanif & Shahab Ud Din & Ning Gui & Tom Holvoet, 2023. "Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem," Mathematics, MDPI, vol. 11(19), pages 1-25, September.
    5. Jose Gonzalez-Velarde & Salvador Garcia-Lumbreras & Alberto Garcia-Diaz, 2008. "A multi-stop routing problem," Annals of Operations Research, Springer, vol. 157(1), pages 153-167, January.
    6. Bock, Stefan, 2010. "Real-time control of freight forwarder transportation networks by integrating multimodal transport chains," European Journal of Operational Research, Elsevier, vol. 200(3), pages 733-746, February.

    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. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    3. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    4. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    5. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    6. Luo, Ying & Schonfeld, Paul, 2007. "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 736-755, August.
    7. Marlin W. Ulmer & Dirk C. Mattfeld & Felix Köster, 2018. "Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests," Transportation Science, INFORMS, vol. 52(1), pages 20-37, January.
    8. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    9. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    10. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, August.
    11. Bock, Stefan, 2010. "Real-time control of freight forwarder transportation networks by integrating multimodal transport chains," European Journal of Operational Research, Elsevier, vol. 200(3), pages 733-746, February.
    12. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    13. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    14. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    15. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    16. Quan Lu & Maged Dessouky, 2004. "An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 503-514, November.
    17. Sam Thangiah & Adel Fergany & Salman Awan, 2007. "Real-time split-delivery pickup and delivery time window problems with transfers," 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. 15(4), pages 329-349, November.
    18. Van Breedam, Alex, 1995. "Improvement heuristics for the Vehicle Routing Problem based on simulated annealing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 480-490, November.
    19. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    20. Nanry, William P. & Wesley Barnes, J., 2000. "Solving the pickup and delivery problem with time windows using reactive tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 107-121, February.

    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:ortrsc:v:38:y:2004:i:4:p:434-446. 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.