The time-dependent profitable pickup and delivery traveling salesman problem with time windows

Research output: Working paperAcademic

161 Downloads (Pure)

Abstract

In this paper we present the time-dependent profitable pickup and delivery traveling salesman problem with time windows (TDPPDTSPTW). The problem consists of determining a tour with a departure time at a depot which maximizes the difference between the collected profit and the total tour duration. Travel times are considered to be time-dependent, i.e. the travel time between two nodes depends on the time the tour starts. This enables to deal with real life challenges such as road congestion. A tailored labeling algorithm with time windows and pickup and delivery (TLTWPD) is developed to find the optimal tour. In the labeling algorithm, new dominance criteria are introduced to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 40 locations and 20 pickup and delivery requests to optimality given a pre-set maximum memory allowance. Furthermore, we present a restricted dynamic programming heuristic algorithm to improve the computation time. This heuristic does not guarantee optimality since it restricts the considered solution space. However, the results of the relatively fast heuristic demonstrate that the solution found is close to optimal (with an average gap of 0.01%).
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages29
Publication statusPublished - 1 Nov 2015

Publication series

NameBETA publicatie : working papers
Volume490
ISSN (Print)1386-9213

Fingerprint Dive into the research topics of 'The time-dependent profitable pickup and delivery traveling salesman problem with time windows'. Together they form a unique fingerprint.

Cite this