IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v19y2019i2d10.1007_s11067-017-9369-7.html
   My bibliography  Save this article

Efficient Insertion Heuristic Algorithms for Multi-Trip Inventory Routing Problem with Time Windows, Shift Time Limits and Variable Delivery Time

Author

Listed:
  • Ampol Karoonsoontawong

    (King Mongkut’s University of Technology Thonburi)

  • Onwasa Kobkiattawin

    (King Mongkut’s University of Technology Thonburi)

  • Chi Xie

    (Shanghai Jiaotong University
    Tongi University)

Abstract

Efficient insertion heuristic algorithms allowing multi trips per vehicle (EIH-MT) and allowing a single trip per vehicle with post-processing greedy heuristic (EIH-ST-GH) are proposed to solve the multi-trip inventory routing problem with time windows, shift time limit and variable delivery time (MTIRPTW-STL-VDT) with short planning horizon. The proposed algorithms are developed based on an original algorithm with two enhancements. First, the delivery volumes, the associated beginning delivery times and the exact profits are calculated and maintained. Second, the process to finalize a best-objective and feasible solution is developed. These algorithms are shown to have the complexity of O(n4). These heuristics maximize the profit function, which is the weighted summation of total delivery volume and negative total travel time. EIH-MT and EIH-ST-GH are performed on 280 instances based on Solomon’s test problems with three weight sets. Best-objective solutions are examined to illustrate the feasibility of various constraints. The trade-offs between total delivery volume and total travel time are observed when varying weight values. There is not a single winner heuristic based on the number-of-vehicles, profit and CPU criteria across the three customer configuration types. On average performance, EIH-ST-GH is preferred over EIH-MT for cluster configuration type with the following average improvement percentages: 1.03% for profit, 2.93% for number-of-vehicles and 38.68% for CPU. For random and random-cluster configuration types, EIH-ST-GH should be preferred because of better profit (0.27% for random and 0.22% for random-cluster) and CPU (46.96% for random and 44.06% for random-cluster) improvements. In the comparison of the multi-trip algorithms against the single-trip algorithm, the benefits in reducing the number of vehicles on-average are shown across all customer configuration types.

Suggested Citation

  • Ampol Karoonsoontawong & Onwasa Kobkiattawin & Chi Xie, 2019. "Efficient Insertion Heuristic Algorithms for Multi-Trip Inventory Routing Problem with Time Windows, Shift Time Limits and Variable Delivery Time," Networks and Spatial Economics, Springer, vol. 19(2), pages 331-379, June.
    • Handle: RePEc:kap:netspa:v:19:y:2019:i:2:d:10.1007_s11067-017-9369-7
    DOI: 10.1007/s11067-017-9369-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11067-017-9369-7
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-017-9369-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. Ricardo Gatica & Pablo Miranda, 2011. "Special Issue on Latin-American Research: A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed," Networks and Spatial Economics, Springer, vol. 11(3), pages 465-485, September.
    2. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    3. Shangyao Yan & Fei-Yen Hsiao & Yi-Chun Chen, 2015. "Inter-School Bus Scheduling Under Stochastic Travel Times," Networks and Spatial Economics, Springer, vol. 15(4), pages 1049-1074, December.
    4. Alegre, Jesus & Laguna, Manuel & Pacheco, Joaquin, 2007. "Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts," European Journal of Operational Research, Elsevier, vol. 179(3), pages 736-746, June.
    5. 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.
    6. Naoki Ando & Eiichi Taniguchi, 2006. "Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows," Networks and Spatial Economics, Springer, vol. 6(3), pages 293-311, September.
    7. Christiansen, Marielle & Fagerholt, Kjetil & Flatberg, Truls & Haugen, Øyvind & Kloster, Oddvar & Lund, Erik H., 2011. "Maritime inventory routing with multiple products: A case study from the cement industry," European Journal of Operational Research, Elsevier, vol. 208(1), pages 86-94, January.
    8. Brandao, Jose & Mercer, Alan, 1997. "A tabu search algorithm for the multi-trip vehicle routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 100(1), pages 180-191, July.
    9. Seyedmehdi Mirmohammadsadeghi & Shamsuddin Ahmed, 2015. "Memetic Heuristic Approach for Solving Truck and Trailer Routing Problems with Stochastic Demands and Time Windows," Networks and Spatial Economics, Springer, vol. 15(4), pages 1093-1115, December.
    10. Patrick Jaillet & Jonathan F. Bard & Liu Huang & Moshe Dror, 2002. "Delivery Cost Approximations for Inventory Routing Problems in a Rolling Horizon Framework," Transportation Science, INFORMS, vol. 36(3), pages 292-300, August.
    11. Awi Federgruen & Paul Zipkin, 1984. "A Combined Vehicle Routing and Inventory Allocation Problem," Operations Research, INFORMS, vol. 32(5), pages 1019-1037, October.
    12. Vishal Gaur & Marshall L. Fisher, 2004. "A Periodic Inventory Routing Problem at a Supermarket Chain," Operations Research, INFORMS, vol. 52(6), pages 813-822, December.
    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. Liu, Gang & He, Jing & Luo, Zhiyong & Yao, Xiaobai & Fan, Qinjin, 2024. "Understanding route choice behaviors' impact on traffic throughput in a dynamic transportation network," Chaos, Solitons & Fractals, Elsevier, vol. 181(C).
    2. Onur Kaya & Dogus Ozkok, 2020. "A Blood Bank Network Design Problem with Integrated Facility Location, Inventory and Routing Decisions," Networks and Spatial Economics, Springer, vol. 20(3), pages 757-783, September.

    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. Yves Crama & Mahmood Rezaei & Martin Savelsbergh & Tom Van Woensel, 2018. "Stochastic Inventory Routing for Perishable Products," Transportation Science, INFORMS, vol. 52(3), pages 526-546, June.
    2. Leandro C. Coelho & Jean-François Cordeau & Gilbert Laporte, 2014. "Thirty Years of Inventory Routing," Transportation Science, INFORMS, vol. 48(1), pages 1-19, February.
    3. Cárdenas-Barrón, Leopoldo Eduardo & González-Velarde, José Luis & Treviño-Garza, Gerardo & Garza-Nuñez, Dagoberto, 2019. "Heuristic algorithm based on reduce and optimize approach for a selective and periodic inventory routing problem in a waste vegetable oil collection environment," International Journal of Production Economics, Elsevier, vol. 211(C), pages 44-59.
    4. M. Alinaghian & M. Ghazanfari & N. Norouzi & H. Nouralizadeh, 2017. "A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 17(4), pages 1185-1211, December.
    5. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    6. Song, Ruidian & Zhao, Lei & Van Woensel, Tom & Fransoo, Jan C., 2019. "Coordinated delivery in urban retail," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 122-148.
    7. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," 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. 25(3), pages 545-560, September.
    8. Zhao, Qiu-Hong & Chen, Shuang & Zang, Cun-Xun, 2008. "Model and algorithm for inventory/routing decision in a three-echelon logistics system," European Journal of Operational Research, Elsevier, vol. 191(3), pages 623-635, December.
    9. Haluk Yapicioglu, 2018. "Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case," Networks and Spatial Economics, Springer, vol. 18(4), pages 773-801, December.
    10. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    11. Jin-Hwa Song & Martin Savelsbergh, 2007. "Performance Measurement for Inventory Routing," Transportation Science, INFORMS, vol. 41(1), pages 44-54, February.
    12. Ramon Faganello Fachini & Vinícius Amaral Armentano & Franklina Maria Bragion Toledo, 2022. "A Granular Local Search Matheuristic for a Heterogeneous Fleet Vehicle Routing Problem with Stochastic Travel Times," Networks and Spatial Economics, Springer, vol. 22(1), pages 33-64, March.
    13. Mojtaba Rajabi-Bahaabadi & Afshin Shariat-Mohaymany & Mohsen Babaei & Daniele Vigo, 2021. "Reliable vehicle routing problem in stochastic networks with correlated travel times," Operational Research, Springer, vol. 21(1), pages 299-330, March.
    14. E-H Aghezzaf, 2008. "Robust distribution planning for supplier-managed inventory agreements when demand rates and travel times are stationary," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1055-1065, August.
    15. 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.
    16. 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.
    17. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    18. 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.
    19. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2015. "Benders Decomposition for Production Routing Under Demand Uncertainty," Operations Research, INFORMS, vol. 63(4), pages 851-867, August.
    20. Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.

    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:kap:netspa:v:19:y:2019:i:2:d:10.1007_s11067-017-9369-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.