A metaheuristic for the delivery man problem with time windows

Ha-Bang Ban ()
Additional contact information
Ha-Bang Ban: Hanoi University of Science and Technology

Journal of Combinatorial Optimization, 2021, vol. 41, issue 4, No 2, 794-816

Abstract: Abstract The Delivery Man Problem with Time Windows (DMPTW) is an extension of the Delivery Man Problem. The objective of DMPTW is to minimize the sum of customers’ arrival time while the deliveries are made during a specific time window given by the customers. Another close variant of objective is a travel duration. In the case, the problem minimizes the sum of travel durations between a depot and customer locations. It has many practical applications to network problems, e.g., whenever servers have to accommodate a set of requests to minimize clients’ total (or average) waiting time. To solve medium to large-sized instances, a two-phase metaheuristic algorithm is proposed. A construction stage generates a feasible solution using Neighborhood Descent with Random neighborhood ordering (RVND), and the optimization stage improves the feasible solution with an Iterated Local Search. Moreover, Tabu Search (TS) is incorporated in the proposed algorithm to prevent it from getting trapped into cycles. Therefore, our algorithm is prevented from becoming stuck at local optima. The results of experimental simulations are compared with well-known and successful metaheuristic algorithms. These results show that the proposed algorithm reaches better solutions in many cases.

Keywords: DMPTW; ILS; TS; and RVND (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00716-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:41:y:2021:i:4:d:10.1007_s10878-021-00716-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00716-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().