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

Research output: Working paperAcademic

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%).
LanguageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages29
StatePublished - 1 Nov 2015

Publication series

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

Fingerprint

Traveling salesman problem
Pickups
Travel time
Labeling
Heuristic algorithms
Dynamic programming
Labels
Profitability
Data storage equipment

Cite this

Sun, P., Dabia, S., Veelenturf, L. P., & van Woensel, T. (2015). The time-dependent profitable pickup and delivery traveling salesman problem with time windows. (BETA publicatie : working papers; Vol. 490). Eindhoven: Technische Universiteit Eindhoven.
Sun, P. ; Dabia, S. ; Veelenturf, L.P. ; van Woensel, T./ The time-dependent profitable pickup and delivery traveling salesman problem with time windows. Eindhoven : Technische Universiteit Eindhoven, 2015. (BETA publicatie : working papers).
@techreport{82e3ccc9d49648e0909adfa0d34c8aff,
title = "The time-dependent profitable pickup and delivery traveling salesman problem with time windows",
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{\%}).",
author = "P. Sun and S. Dabia and L.P. Veelenturf and {van Woensel}, T.",
year = "2015",
month = "11",
day = "1",
language = "English",
series = "BETA publicatie : working papers",
publisher = "Technische Universiteit Eindhoven",
type = "WorkingPaper",
institution = "Technische Universiteit Eindhoven",

}

Sun, P, Dabia, S, Veelenturf, LP & van Woensel, T 2015 'The time-dependent profitable pickup and delivery traveling salesman problem with time windows' BETA publicatie : working papers, vol. 490, Technische Universiteit Eindhoven, Eindhoven.

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 paperAcademic

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 -

Sun P, Dabia S, Veelenturf LP, van Woensel T. The time-dependent profitable pickup and delivery traveling salesman problem with time windows. Eindhoven: Technische Universiteit Eindhoven. 2015 Nov 1, (BETA publicatie : working papers).