IDEAS home Printed from https://ideas.repec.org/a/spr/telsys/v78y2021i4d10.1007_s11235-021-00833-7.html
   My bibliography  Save this article

Compact Sine Cosine Algorithm applied in vehicle routing problem with time window

Author

Listed:
  • Jeng-Shyang Pan

    (Shandong University of Science and Technology)

  • Qing-yong Yang

    (Shandong University of Science and Technology)

  • Shu-Chuan Chu

    (Shandong University of Science and Technology)

  • Kuo-Chi Chang

    (Fujian University of Technology)

Abstract

In this paper, the compact Sine Cosine Algorithm (cSCA) is proposed. The cSCA algorithm is not based on population, but simulates the behavior of the actual population through a probability model called virtual population. Compared with the original algorithm, the cSCA algorithm takes up less memory space. However, frequent sampling may lead to poor solution quality. In view of this situation, this paper introduces the intergenerational generation sampling mechanism to improve the cSCA algorithm. Through the CEC2013 function set test, compared with the original SCA algorithm and other compact algorithms, the algorithm proposed in this paper can show strong solving ability. Finally, this paper describes how to apply the proposed algorithm and the SCA algorithm to solve the vehicle routing problem with time window in transportation. The quality of the solution is further improved by introducing the relocate operator. Through Solomon standard test data, the calculation performance of the algorithms is verified.

Suggested Citation

  • Jeng-Shyang Pan & Qing-yong Yang & Shu-Chuan Chu & Kuo-Chi Chang, 2021. "Compact Sine Cosine Algorithm applied in vehicle routing problem with time window," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 78(4), pages 609-628, December.
    • Handle: RePEc:spr:telsys:v:78:y:2021:i:4:d:10.1007_s11235-021-00833-7
    DOI: 10.1007/s11235-021-00833-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11235-021-00833-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11235-021-00833-7?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
    ---><---

    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    2. Olli Bräysy & Michel Gendreau, 2002. "Tabu Search heuristics for the Vehicle Routing Problem with Time Windows," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 10(2), pages 211-237, December.
    3. Jonathan F. Bard & George Kontoravdis & Gang Yu, 2002. "A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 36(2), pages 250-269, May.
    4. 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.
    5. 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.
    6. Wang, Feng & Zhang, Jian & Xu, Xing & Cai, Yingfeng & Zhou, Zhiguang & Sun, Xiaoqiang, 2019. "A comprehensive dynamic efficiency-enhanced energy management strategy for plug-in hybrid electric vehicles," Applied Energy, Elsevier, vol. 247(C), pages 657-669.
    7. É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.
    8. Ai-Qing Tian & Shu-Chuan Chu & Jeng-Shyang Pan & Huanqing Cui & Wei-Min Zheng, 2020. "A Compact Pigeon-Inspired Optimization for Maximum Short-Term Generation Mode in Cascade Hydroelectric Power Station," Sustainability, MDPI, vol. 12(3), pages 1-19, January.
    9. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    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. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    2. Schneider, Michael, 2016. "The vehicle-routing problem with time windows and driver-specific times," European Journal of Operational Research, Elsevier, vol. 250(1), pages 101-119.
    3. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    4. 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.
    5. Schyns, M., 2015. "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, Elsevier, vol. 245(3), pages 704-718.
    6. Ciancio, Claudio & Laganá, Demetrio & Vocaturo, Francesca, 2018. "Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 267(1), pages 187-199.
    7. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    8. Cortés, Cristián E. & Gendreau, Michel & Rousseau, Louis Martin & Souyris, Sebastián & Weintraub, Andrés, 2014. "Branch-and-price and constraint programming for solving a real-life technician dispatching problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 300-312.
    9. Fröhlich von Elmbach, Alexander & Scholl, Armin & Walter, Rico, 2019. "Minimizing the maximal ergonomic burden in intra-hospital patient transportation," European Journal of Operational Research, Elsevier, vol. 276(3), pages 840-854.
    10. 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.
    11. 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.
    12. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    13. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    14. 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.
    15. Olli Bräysy & Wout Dullaert & Geir Hasle & David Mester & Michel Gendreau, 2008. "An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 371-386, August.
    16. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    17. Ehsan Khodabandeh & Lihui Bai & Sunderesh S. Heragu & Gerald W. Evans & Thomas Elrod & Mark Shirkness, 2017. "Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting," International Journal of Production Research, Taylor & Francis Journals, vol. 55(4), pages 1100-1116, February.
    18. 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.
    19. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    20. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.

    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:spr:telsys:v:78:y:2021:i:4:d:10.1007_s11235-021-00833-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.