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

摘要

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(n(4)). 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.