The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree

The Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSP-PD)[1] can be defined on an undirected graph

T

=(

V

,

E

), where

V

is a set of

n

vertices and

E

is a set of edges. A nonnegative weight

d

(

e

) is associated with each edge

e

∈

E

to indicate its length. Each vertex is either a pickup point, a delivery point, or a transient point. At each pickup point is a load of unit size that can be shipped to any delivery point which requests a load of unit size. Hence we can use

a

(

v

)=1,0,–1 to indicate

v

to be a pickup, a transient, or a delivery point, and

a

(

v

) is referred to as the volume of

v

. The total volumes for pickups and for deliveries are usually assumed to be balanced, i.e.,

$\sum_{v\in {\it V}}{\it a}({\it v})=0$

, which implies that all loads in pickup points must be shipped to delivery points [1]. Among

V

, one particular vertex

r

∈

V

is designated as a depot, at which a vehicle of limited capacity of

k

≥ 1 starts and ends. The problem aims to determine a minimum length feasible route that picks up and delivers all loads without violating the vehicle capacity.