### 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*. (BETA publicatie : working papers; Vol. 490). Eindhoven: Technische Universiteit Eindhoven.

}

**The time-dependent profitable pickup and delivery traveling salesman problem with time windows.** / Sun, P.; Dabia, S.; Veelenturf, L.P.; van Woensel, T.

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 -