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. 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.
    2. 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.
    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. 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.
    5. 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.
    6. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    7. 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).
    8. 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.
    9. 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.
    10. 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).
    11. 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.
    12. 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.
    13. 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.
    14. 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).
    15. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    16. Yeo, Lip Siang & Teng, Sin Yong & Ng, Wendy Pei Qin & Lim, Chun Hsion & Leong, Wei Dong & Lam, Hon Loong & Wong, Yat Choy & Sunarso, Jaka & How, Bing Shen, 2022. "Sequential optimization of process and supply chains considering re-refineries for oil and gas circularity," Applied Energy, Elsevier, vol. 322(C).
    17. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    18. Martinhon, Carlos & Lucena, Abilio & Maculan, Nelson, 2004. "Stronger K-tree relaxations for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(1), pages 56-71, October.
    19. Ling Gai & Ying Jin & Binyuan Zhang, 2022. "An integrated method for hybrid distribution with estimation of demand matching degree," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2782-2808, November.
    20. Jin Li & Feng Wang & Yu He, 2020. "Electric Vehicle Routing Problem with Battery Swapping Considering Energy Consumption and Carbon Emissions," Sustainability, MDPI, vol. 12(24), pages 1-20, December.

    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.