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

Ampol Karoonsoontawong (), Onwasa Kobkiattawin () and Chi Xie ()
Additional contact information
Ampol Karoonsoontawong: King Mongkut’s University of Technology Thonburi
Onwasa Kobkiattawin: King Mongkut’s University of Technology Thonburi
Chi Xie: Shanghai Jiaotong University

Networks and Spatial Economics, 2019, vol. 19, issue 2, No 1, 379 pages

Abstract: 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.

Keywords: Inventory routing problem; Insertion heuristic; Multi trip (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-017-9369-7 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:19:y:2019:i:2:d:10.1007_s11067-017-9369-7

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-017-9369-7

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().