Abstract
We present novel branch-and-check and logic-based Benders decomposition techniques for the Travelling Purchaser Problem, an important optimization problem with applications in vehicle routing, logistics, and warehouse management. Our master problem determines a set of markets and directed travel arcs that satisfy product purchase constraints with relaxed travel costs. Our subproblem identifies subtours within this master assignment and produces a set of generalized subtour elimination cuts. We show that the proposed technique demonstrates strong performance on the asymmetric problem variants, finding optimal solutions to previously unsolved instances, while performing competitively on a number of symmetric problem classes. Furthermore, our model is implemented unchanged for the four problem variants whereas other state-of-the-art approaches are variant-specific.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The limit of one per iteration is due to the depot inclusion condition.
- 2.
Experiments using dynamic variable creation in SCIP [1] show a relative improvement in B&C compared to LBBD though both CPLEX implementations are faster.
References
Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)
Applegate, D., Bixby, R., Cook, W., Chvátal, V.: On the solution of traveling salesman problems. Rheinische Friedrich-Wilhelms-Universität Bonn (1998)
Balas, E., Toth, P.: Branch and bound methods for the traveling salesman problem. Technical report MSRR-488, DTIC Document (1983)
Beck, J.C.: Checking-up on branch-and-check. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 84–98. Springer, Heidelberg (2010)
Bontoux, B., Feillet, D.: Ant colony optimization for the traveling purchaser problem. Comput. Oper. Res. 35(2), 628–637 (2008)
Burt, C.N., Lipovetzky, N., Pearce, A.R., Stuckey, P.J.: Approximate uni-directional benders decomposition. In: Proceedings of PlanSOpt-15 Workshop on Planning, Search and Optimization AAAI-15 (2015)
Cambazard, H., Penz, B.: A constraint programming approach for the traveling purchaser problem. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 735–749. Springer, Heidelberg (2012)
Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1), 27–36 (1991)
Erlenkotter, D.: A dual-based procedure for uncapacitated facility location. Oper. Res. 26(6), 992–1009 (1978)
Flood, M.M.: The traveling-salesman problem. Oper. Res. 4(1), 61–75 (1956)
Geoffrion, A.M.: Generalized benders decomposition. J. Optim. Theor. Appl. 10(4), 237–260 (1972)
Goerler, A., Schulte, F., Voß, S.: An application of late acceptance hill-climbing to the traveling purchaser problem. In: Pacino, D., Voß, S., Jensen, R.M. (eds.) ICCL 2013. LNCS, vol. 8197, pp. 173–183. Springer, Heidelberg (2013)
Goldbarg, M.C., Bagi, L.B., Goldbarg, E.F.G.: Transgenetic algorithm for the traveling purchaser problem. Eur. J. Oper. Res. 199(1), 36–45 (2009)
Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logistics (NRL) 34(3), 307–318 (1987)
Hooker, J.N., Ottosson, G.: Logic-based benders decomposition. Math. Program. 96(1), 33–60 (2003)
Laporte, G.: Generalized subtour elimination constraints and connectivity constraints. J. Oper. Res. Soc. 37, 509–514 (1986)
Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)
Laporte, G., Nobert, Y.: A cutting planes algorithm for the m-salesmen problem. J. Oper. Res. Soc. 31, 1017–1023 (1980)
Laporte, G., Riera-Ledesma, J., Salazar-González, J.-J.: A branch-and-cut algorithm for the undirected traveling purchaser problem. Oper. Res. 51(6), 940–951 (2003)
Miliotis, P.: Integer programming approaches to the travelling salesman problem. Math. Program. 10(1), 367–378 (1976)
Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326–329 (1960)
Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60–100 (1991)
Ramesh, T.: Traveling purchaser problem. Opsearch 18(1–3), 78–91 (1981)
Riera-Ledesma, J., Salazar-González, J.-J.: Solving the asymmetric traveling purchaser problem. Ann. Oper. Res. 144(1), 83–97 (2006)
Singh, K.N., van Oudheusden, D.L.: A branch and bound algorithm for the traveling purchaser problem. Eur. J. Oper. Res. 97(3), 571–579 (1997)
Thorsteinsson, E.S.: Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 16–30. Springer, Heidelberg (2001)
Tran, T.T., Araujo, A., Beck, J.C.: Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28(1), 83–95 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Booth, K.E.C., Tran, T.T., Beck, J.C. (2016). Logic-Based Decomposition Methods for the Travelling Purchaser Problem. In: Quimper, CG. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2016. Lecture Notes in Computer Science(), vol 9676. Springer, Cham. https://doi.org/10.1007/978-3-319-33954-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-33954-2_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-33953-5
Online ISBN: 978-3-319-33954-2
eBook Packages: Computer ScienceComputer Science (R0)