Efficient insertion heuristics for multitrip vehicle routing problem with time windows and shift time limits

Journal article

Authors/Editors

AMPOL KAROONSOONTAWONG

Strategic Research Themes

No matching items found.

Publication Details

Author list: Karoonsoontawong A.

Publisher: SAGE Publications

Publication year: 2015

Journal: Transportation Research Record: Journal of the Transportation Research Board (0361-1981)

Volume number: 2477

Issue number: 2477

Start page: 27

End page: 39

Number of pages: 13

ISSN: 0361-1981

eISSN: 2169-4052

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84975856236&doi=10.3141%2f2477-04&partnerID=40&md5=82c4eeb863f286bf9daa48dd1878afa5

Languages: English-Great Britain (EN-GB)

View in Web of Science | View on publisher site | View citing articles in Web of Science

Abstract

The modified efficient insertion heuristic that allows multiple trips per vehicle (MEIH-MT) and one that allows a single trip per vehicle with a postprocessing greedy heuristic (MEIH-ST-GH) to construct a multitrip solution are proposed to solve the multitrip vehicle routing problem with time windows and shift time limits. The modifications to the original heuristic enforce the bounds of the forward shift of the earliest departure time of the vehicle and the backward shift of the latest completion time of the vehicle due to an insertion to guarantee a consistent and feasible solution. The overall complexities of both heuristics are the same as those of the original heuristic, O(n3 ). MEIH-MT and MEIH-ST-GH are performed on 280 instances based on Solomon's test problems. There is no clear winner on the basis of the number of vehicles and total travel time, whereas MEIH-MT is worse than MEIH-ST-GH on computer processing time in all instances. For cluster instances, MEIH-MT should be preferred because it is on average better than MEIH-ST-GH by two criteria: 1.91% on number of vehicles and 0.77% on total travel time. For random-cluster instances, MEIH-MT should be preferred because it is better than MEIH-ST-GH by two criteria: 9.02% on number of vehicles and 5.56% on total travel time. For random instances, MEIH-ST-GH should be preferred because MEIH-MT is outperformed by MEIH-ST-GH by two criteria: 70.92% on processing time and 12.41% on number of vehicles. Thus, MEIH-MT should be preferred over MEIH-ST-GH for the problem instances with clustered customer locations, and MEIH-ST-GH should be preferred for the problem instances with random customer locations.

Keywords