TRB Pubsindex
Text Size:
x

« Prev Next »

Return to Results | New Search

Bookmark and Share

Title:

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

Accession Number:

01588157

Record Type:

Component

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

Supplemental Notes:

This paper was sponsored by TRB committee AT015 Standing Committee on Freight Transportation Planning and Logistics.

Monograph Accession #:

01584066

Report/Paper Numbers:

16-1215

Language:

English

Corporate Authors:

Transportation Research Board

500 Fifth Street, NW
Washington, DC 20001 United States

Authors:

Karoonsoontawong, Ampol

Pagination:

24p

Publication Date:

2016

Conference:

Transportation Research Board 95th Annual Meeting

Location: Washington DC, United States
Date: 2016-1-10 to 2016-1-14
Sponsors: Transportation Research Board

Media Type:

Digital/other

Features:

Figures; References; Tables

Subject Areas:

Freight Transportation; Planning and Forecasting; I72: Traffic and Transport Planning

Source Data:

Transportation Research Board Annual Meeting 2016 Paper #16-1215

Files:

TRIS, TRB, ATRI

Created Date:

Jan 12 2016 4:33PM