A branch-and-cut algorithm for the preemptive swapping problem. (English) Zbl 1247.90072
Summary: In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch-and-cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 05C90 | Applications of graph theory |
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | Anily, The swapping problem, Networks 22 pp 419– (1992) · Zbl 0763.90080 · doi:10.1002/net.3230220408 |
| [2] | Anily, The swapping problem on a line, SIAM J Comput 29 pp 327– (1999) · Zbl 0938.90012 · doi:10.1137/S0097539797323108 |
| [3] | Anily, The preemptive swapping problem on a tree, Networks, In press · Zbl 1233.90075 |
| [4] | Applegate, Concorde TSP solver (2007) |
| [5] | Ascheuer, A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints, Comput Optim Appl 17 pp 61– (2000) · Zbl 1017.90095 · doi:10.1023/A:1008779125567 |
| [6] | Balas, The precedence-constrained asymmetric traveling salesman polytope, Math Program 68 pp 241– (1995) · Zbl 0835.90109 · doi:10.1007/BF01585767 |
| [7] | Bordenave, A branch-and-cut algorithm for the non-preemptive swapping problem, Naval Res Logistics 56 pp 478– (2009) · Zbl 1182.90011 · doi:10.1002/nav.20361 |
| [8] | Bordenave, Heuristics for the mixed swapping problem, Comput Oper Res 37 pp 108– (2010) · Zbl 1171.90331 · doi:10.1016/j.cor.2009.03.032 |
| [9] | Chvátal, Edmonds polytopes and weakly hamiltonian graphs, Math Program 5 pp 29– (1973) · Zbl 0267.05118 · doi:10.1007/BF01580109 |
| [10] | Desrochers, Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Oper Res Lett 10 pp 27– (1991) · Zbl 0723.90081 · doi:10.1016/0167-6377(91)90083-2 |
| [11] | Escudero, An inexact algorithm for the sequential ordering problem, Eur J Oper Res 37 pp 236– (1988) · Zbl 0653.90036 · doi:10.1016/0377-2217(88)90333-5 |
| [12] | Goldberg, A new approach to the maximum-flow problem, J ACM 35 pp 921– (1988) · Zbl 0661.90031 · doi:10.1145/48014.61051 |
| [13] | Grötschel, On the symmetric traveling salesman problem I: Inequalities, Math Program 16 pp 265– (1979) · Zbl 0413.90048 · doi:10.1007/BF01582116 |
| [14] | Hao, A faster algorithm for finding the minimum cut in a graph (1992) · Zbl 0829.68095 |
| [15] | Hernández-Pérez, A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Discrete Appl Math 145 pp 126– (2004) · Zbl 1058.90054 · doi:10.1016/j.dam.2003.09.013 |
| [16] | Hernández-Pérez, The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms, Networks 50 pp 258– (2007) · Zbl 1146.90056 · doi:10.1002/net.20209 |
| [17] | Letchford, Multistars, partial multistars and the capacitated vehicle routing problem, Math Program 94 pp 21– (2002) · Zbl 1023.90073 · doi:10.1007/s10107-002-0336-8 |
| [18] | Lysgaard, CVRPSEP package (2007) |
| [19] | Lysgaard, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math Program 100 pp 423– (2004) · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8 |
| [20] | Miller, Integer programming formulations and traveling salesman problems, J ACM 7 pp 326– (1960) · Zbl 0100.15101 · doi:10.1145/321043.321046 |
| [21] | Naddef, Efficient separation routines for the symmetric traveling salesman problem I: General tools and comb separation, Math Program 92 pp 237– (2002) · Zbl 1007.90053 · doi:10.1007/s101070100275 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
