Abstract
| Language | English |
|---|---|
| Place of Publication | Eindhoven |
| Publisher | Technische Universiteit Eindhoven |
| Number of pages | 29 |
| State | Published - 1 Nov 2015 |
Publication series
| Name | BETA publicatie : working papers |
|---|---|
| Volume | 490 |
| ISSN (Print) | 1386-9213 |
Fingerprint
Cite this
}
The time-dependent profitable pickup and delivery traveling salesman problem with time windows. / Sun, P.; Dabia, S.; Veelenturf, L.P.; van Woensel, T.
Eindhoven : Technische Universiteit Eindhoven, 2015. (BETA publicatie : working papers; Vol. 490).Research output: Working paper › Academic
TY - UNPB
T1 - The time-dependent profitable pickup and delivery traveling salesman problem with time windows
AU - Sun,P.
AU - Dabia,S.
AU - Veelenturf,L.P.
AU - van Woensel,T.
PY - 2015/11/1
Y1 - 2015/11/1
N2 - 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%).
AB - 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%).
M3 - Working paper
T3 - BETA publicatie : working papers
BT - The time-dependent profitable pickup and delivery traveling salesman problem with time windows
PB - Technische Universiteit Eindhoven
CY - Eindhoven
ER -