IDEAS home Printed from https://ideas.repec.org/p/zbw/tudiwv/22017.html
   My bibliography  Save this paper

A genetic algorithm for vehicle routing problems with temporal synchronization constraints

Author

Listed:
  • Hocke, Stephan
  • Gajewski, Christina
  • Kasper, Mathias

Abstract

This paper presents a Genetic Algorithm for the Vehicle Routing and Scheduling Problem with time windows and temporal synchronization constraints. That means that as opposed to the usual procedure, in addition to the usual task covering, some vertices must be served by more than one vehicle at the same time. The chromosome coding used here is based on a proposed solution representation by Mankowska et al. [19]. The Genetic Algorithm is able to solve their instance types up to 20 vertices near to optimality. Even in greater instances with 100 vertices the solution quality of the Genetic Algorithm outperforms the Local Search presented by Mankowska et al. [19], however with losses in runtime. In order to get more comparable results, both solution approaches are evaluated at the well-known benchmark instances of Bredstrom and Ronnqvist [6]. This includes the presentation of a simple repair algorithm during the chromosome crossover based on an insertion heuristic in order to achieve the hard time window constraints of the benchmarks.

Suggested Citation

  • Hocke, Stephan & Gajewski, Christina & Kasper, Mathias, 2017. "A genetic algorithm for vehicle routing problems with temporal synchronization constraints," Discussion Papers 2/2017, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    • Handle: RePEc:zbw:tudiwv:22017
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/233869/1/1757099182.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    3. C-A Amaya & A Langevin & M Trépanier, 2010. "A heuristic method for the capacitated arc routing problem with refill points and multiple loads," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1095-1103, July.
    Full references (including those not matched with items on IDEAS)

    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. Ertan Yakıcı & Robert F. Dell & Travis Hartman & Connor McLemore, 2018. "Daily aircraft routing for amphibious ready groups," Annals of Operations Research, Springer, vol. 264(1), pages 477-498, May.
    2. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    3. Jumbo, Olga & Moghaddass, Ramin, 2022. "Resource optimization and image processing for vegetation management programs in power distribution networks," Applied Energy, Elsevier, vol. 319(C).
    4. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    5. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    6. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    7. Tianlu Zhao & Yongjian Yang & En Wang, 2020. "Minimizing the average arriving distance in carpooling," International Journal of Distributed Sensor Networks, , vol. 16(1), pages 15501477198, January.
    8. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    9. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    10. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    11. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.
    12. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    13. Y H Lee & J I Kim & K H Kang & K H Kim, 2008. "A heuristic for vehicle fleet mix problem using tabu search and set partitioning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 833-841, June.
    14. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    15. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    16. Tibor Holczinger & Olivér Ősz & Máté Hegyháti, 2020. "Scheduling approach for on-site jobs of service providers," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 913-948, December.
    17. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    18. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    19. Narjes MASHHADI BANDANI & Alireza NADERI & Mohsen AKBARPOUR SHIRZAEI, 2017. "Cement Transportation Limited-Fleet Modeling And Assigning To Rated Demands," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 12(1), pages 111-123, March.
    20. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).

    More about this item

    Statistics

    Access and download statistics

    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:zbw:tudiwv:22017. 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: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/iwtudde.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.