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

บทความในวารสาร

ผู้เขียน/บรรณาธิการ

อำพล การุณสุนทวงษ์

กลุ่มสาขาการวิจัยเชิงกลยุทธ์

ไม่พบข้อมูลที่เกี่ยวข้อง

รายละเอียดสำหรับงานพิมพ์

รายชื่อผู้แต่ง: Karoonsoontawong A.

ผู้เผยแพร่: SAGE Publications

ปีที่เผยแพร่ (ค.ศ.): 2015

วารสาร: Transportation Research Record: Journal of the Transportation Research Board (0361-1981)

Volume number: 2477

Issue number: 2477

หน้าแรก: 27

หน้าสุดท้าย: 39

จำนวนหน้า: 13

นอก: 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

ภาษา: English-Great Britain (EN-GB)

ดูในเว็บของวิทยาศาสตร์ | ดูบนเว็บไซต์ของสำนักพิมพ์ | บทความในเว็บของวิทยาศาสตร์

บทคัดย่อ

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.

คำสำคัญ