Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11602613_105 | ISAAC |
Keywords | Field | DocType |
limited capacity,particular vertex,delivery point,n vertex,salesman problem,transient point,minimum length,pickup point,unit size,vehicle capacity,traveling salesman problem | Approximation algorithm,Delivery point,Discrete mathematics,Graph,Combinatorics,Tree (graph theory),Vertex (geometry),Travelling salesman problem,Pickup,Mathematics | Conference |
Volume | ISSN | ISBN |
3827 | 0302-9743 | 3-540-30935-7 |
Citations | PageRank | References |
3 | 0.95 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Lim | 1 | 937 | 89.78 |
| Fan Wang | 2 | 142 | 9.55 |
| Zhou Xu | 3 | 14 | 2.71 |