Multi-Trip Time-Dependent Vehicle Routing Problem with Soft Time Windows and Overtime Constraints

Ampol Karoonsoontawong (), Puntipa Punyim (), Wanvara Nueangnitnaraporn () and Vatanavongs Ratanavaraha ()
Additional contact information
Ampol Karoonsoontawong: King Mongkut’s University of Technology Thonburi
Puntipa Punyim: King Mongkut’s University of Technology Thonburi
Wanvara Nueangnitnaraporn: Transportation Engineer, Systra MVA (Thailand) Limited
Vatanavongs Ratanavaraha: Suranaree University of Technology

Networks and Spatial Economics, 2020, vol. 20, issue 2, No 9, 549-598

Abstract: Abstract The multi-trip time-dependent vehicle routing problem with soft time windows and overtime constraints (MT-TDVRPSTW-OT) is considered in this paper. The modified hierarchical multi-objective formulation and the equivalent single-objective formulation are proposed. The iterative multi-trip tour construction and improvement (IMTTCI) procedure and the single-trip tour counterpart procedure with post-processing greedy heuristic (ISTTCI-GH) are proposed to solve the problem. These procedures are based on the ruin and recreate principle, and consider trade-offs among cost components (vehicle usage, number of early/late soft time window occurrences, transport distance, transport time, overtime and early/late soft time window penalty costs) in the search process. From the computational experiment, the IMTTCI procedure outperforms the existing efficient insertion heuristic with 42.09% improvement in number of vehicles and 24.30% improvement in travel time for the constant-speed multi-trip vehicle routing problem with hard time windows and shift time limits, a special case of MT-TDVRPSTW-OT problem, on all problem instances. For the MT-TDVRPSTW-OT problem, the ISTTCI-GH and the IMTTCI outperform the ISTTCI on all problem groups by 43.21% and 69.44% in the number of vehicles (the primary objective), respectively. The IMTTCI outperforms the ISTTCI-GH in number of vehicles by 51.07%, but takes 42.83% longer CPU time than the ISTTCI-GH. The performance of IMTTCI in terms of the primary objective improves with the increase of mean speed as well as the increase of time window width and planning horizon across all customer configuration types, tighter/looser time windows, shorter/longer planning horizon and various time-dependent travel speed profiles. The sensitivity analysis of different problem parameters is performed. The complexity analysis of the proposed procedures shows that the proposed procedures are solvable in polynomial time, and from the computational results the relationships between the CPU time and problem size confirm this. For the MT-VRPSTW-OT, a mixed integer program and the special case of MT-TDVRPSTW-OT, on 12-customer instances, the proposed IMTTCI algorithm yields the average optimality gap of 1.35% with the average CPU time of 0.66 seconds, whereas the GAMS/CPLEX solver yields the average optimality gap of 0.83% with the average CPU time of 256.39 seconds. The proposed IMTTCI algorithm yields only 0.52% greater optimality gap but 388 times faster CPU time than the commercial solver.

Keywords: Time Dependent Vehicle Routing Problem; Multi Trip; Soft Time Window; Shift Time Limit; Overtime (search for similar items in EconPapers)
Date: 2020
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-019-09492-3 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:20:y:2020:i:2:d:10.1007_s11067-019-09492-3

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

DOI: 10.1007/s11067-019-09492-3

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