The unit capacity pickup and delivery problem on a one-way loop (Q800829): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 02:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The unit capacity pickup and delivery problem on a one-way loop |
scientific article |
Statements
The unit capacity pickup and delivery problem on a one-way loop (English)
0 references
1984
0 references
We consider the problem of making pickups and deliveries of one unit on a one-way loop with a vehicle of unit capacity. The problem is shown to be equivalent to a travelling salesman problem with distance matrix given by \((a_ j\)-b\({}_ i)\) (modulo r) where \(a_ j\) and \(b_ i\) are the locations of the pickup and delivery points for the jth and ith customers, respectively and r is the circumference of the loop. Following the work of Gilmore and Gomory on a related problem, an optimal solution is found in polynomial time by solving the relaxed assignment problem and patching any resulting subtours. Finally it is shown that the model applies to a problem of minimization of wallpaper waste.
0 references
pickups and deliveries
0 references
one-way loop
0 references
travelling salesman
0 references
optimal solution
0 references
polynomial time
0 references
relaxed assignment problem
0 references