×

An exact algorithm for the capacitated shortest spanning arborescence. (English) Zbl 0844.90104

Summary: We are given a complete and loop-free digraph \(G = (V,A)\), where \(V = \{1, \dots, n\}\) is the vertex set, \(A = \{(i,j) : i,j \in V\}\) the arc set, and \(r \in V\) is a distinguished root vertex. For each arc \((i,j) \in A\), let \(c_{ij}\) be the associated cost, and for each vertex \(i\), let \(q_i \geq 0\) be the associated demand (with \(q_r = 0)\). Moreover, a nonnegative branch capacity, \(Q\), is defined. A Capacitated Shortest Spanning Arborescence rooted at \(r(CSSA_r)\) is a minimum cost partial digraph such that: (i) each vertex \(j \neq r\) has exactly one entering arc; (ii) for each vertex \(j \neq r\), a path from \(r\) to \(j\) exists; (iii) for each branch leaving vertex \(r\), the total demand of the vertices does not exceed the branch capacity, \(Q\). A variant of the \(CSSA_r\) problem (called \(D - CSSA_r)\) arises when the out-degree of the root vertex is constrained to be equal to a given value \(D\). These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound for \(CSSA_r\) and \(D - CSSA_r\) problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.

MSC:

90C35 Programming involving graphs or networks
93C10 Nonlinear systems in control theory

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows (Prentice-Hall, 1993). · Zbl 1201.90001
[2] M. Bellmore and J.C. Malone, Pathology of travelling salesman subtour-elimination algorithms, Operations Research 19(1971)278–307. · Zbl 0219.90032 · doi:10.1287/opre.19.2.278
[3] G. Carpaneto, M. Dell’Amico, M. Fischetti and P. Toth, A branch and bound algorithm for the multiple depot vehicle scheduling problem, Networks 19(1989)531–548. · Zbl 0672.90073 · doi:10.1002/net.3230190505
[4] G. Carpaneto, M. Fischetti and P. Toth, New lower bounds for the symmetric travelling salesman problem, Mathematical Programming 45(1989)233–254. · Zbl 0682.90093 · doi:10.1007/BF01589105
[5] K.M. Chandy and T. Lo, The capacitated minimum spanning tree, Networks 3(1973)173–182. · Zbl 0256.90016 · doi:10.1002/net.3230030204
[6] J. Edmonds, Optimum branching, J. Res. Nat. Bur. Standards 71B(1967)233–240. · Zbl 0155.51204
[7] D. Elias and M.J. Ferguson, Topological design of multipoint teleprocessing networks, IEEE Transactions on Communications COM-22(1974)1753–1762. · doi:10.1109/TCOM.1974.1092122
[8] M. Fischetti and P. Toth, An additive approach for the optimal solution of the prize-collecting travelling salesman problem, in:Vehicle Routing: Methods and Studies, eds. B.L. Golden and A.A. Assad (North-Holland, Amsterdam, 1988). · Zbl 0686.90029
[9] M. Fischetti and P. Toth, A new dominance procedure for combinatorial optimization problems, Operations Research Letters 7(1988)181–187. · Zbl 0655.90064 · doi:10.1016/0167-6377(88)90025-9
[10] M. Fischetti and P. Toth, An Additive Bounding Procedure for Combinatorial Optimization Problems, Operations Research 37(1989)319–328. · Zbl 0676.90049 · doi:10.1287/opre.37.2.319
[11] M. Fischetti and P. Toth, An additive bounding procedure for the asymmetric travelling salesman problem, Mathematical Programming 53(1992)173–197. · Zbl 0773.90082 · doi:10.1007/BF01585701
[12] M. Fischetti and P. Toth, An efficient algorithm for the min-sum arborescence problem on complete digraphs, ORSA Journal on Computing 5(1993)426–434. · Zbl 0789.90082
[13] M. Fischetti, P. Toth and D. Vigo, A branch and bound algorithm for the capacitated vehicle routing problem on directed graphs, Operations Research 42(1994)846–859. · Zbl 0815.90065 · doi:10.1287/opre.42.5.846
[14] M.L. Fisher, Optimal solution of vehicle routing problems using minimumk-trees, Operations Research 42(1994)626–642. · Zbl 0815.90066 · doi:10.1287/opre.42.4.626
[15] H.N. Gabow and R.E. Tarjan, Efficient algorithms for a family of matroid intersection problems, Journal of Algorithms 5(1984)80–131. · Zbl 0545.05029 · doi:10.1016/0196-6774(84)90042-7
[16] B. Gavish, Formulations and algorithms for the capacitated minimal directed tree problem, Journal of the Association for Computing Machinery 30(1983)118–132. · Zbl 0504.90052
[17] A. Kershenbaum, Computing capacitated minimal spanning trees efficiently, Networks 4(1974)299–310. · Zbl 0311.90070 · doi:10.1002/net.3230040403
[18] M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees, Operations Research 18(1970)1138–1162. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[19] M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees: Part II, Mathematical Programming 1(1971)6–25. · Zbl 0232.90038 · doi:10.1007/BF01584070
[20] S. Martello and P. Toth,Knapsack Problems: Algorithms and Computer Implementations (Wiley, Chichester, 1990). · Zbl 0708.68002
[21] K. Malik and G. Yu, A branch and bound algorithm for the capacitated minimum spanning tree problem, Networks 23(1993)525–532. · Zbl 0793.90090 · doi:10.1002/net.3230230603
[22] C.H. Papadimitriou, The complexity of the capacitated tree problem, Networks 8(1978)217–230. · Zbl 0443.68048 · doi:10.1002/net.3230080306
[23] R.E. Tarjan, Finding optimum branchings, Networks 7(1977)25–35. · Zbl 0379.90100 · doi:10.1002/net.3230070103
[24] P. Toth and D. Vigo, An exact algorithm for the vehicle routing problem with backhauls, Research Report, DEIS OR/93/5, University of Bologna (1993). · Zbl 0919.90057
[25] G. Yu and M.L. Fisher, A Lagrangian optimization algorithm for the asymmetric non-uniform fleet vehicle routing problem, Working Paper 89-03-10, Decision Science Department, The Wharton School, University of Pennsylvania (1989).
[26] D. Vigo, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, European Journal of Operational Research, to appear. · Zbl 0908.90115
[27] G. Laporte, H. Mercure and Y. Nobert, An exact algorithm for the asymmetrical capacitated vehicle routing problem, Networks 16(1986)33–46. · Zbl 0643.90034 · doi:10.1002/net.3230160104
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.