A comparative study of the capability of alternative mixed integer programming formulations
In selecting the best mixed integer linear programming (MILP) formulation the important issue is to figure out how to evaluate the performance of each candidate formulation in terms of selected criteria. The main objective of this study is to propose a systematic approach to guide the selection of the best MILP formulation among the alternatives according to the needs of the decision maker. For this reason we consider the problem of “selecting the most appropriate MILP formulation for a certain type of decision maker” as a multi-criteria decision making problem and present an integrated AHP-TOPSIS decision making methodology to select the most appropriate formulation. As an example the proposed decision making methodology is implemented on the selection of the MILP formulations of the Capacitated Vehicle Routing Problem (CVRP). A numerical example is provided for illustrative purposes. As a result, the proposed decision model can be a tool for the decision makers (here they are the scientists, engineers and practitioners) who intend to choose the appropriate mathematical model(s) among the alternatives according to their needs on their studies. The integrated AHP-TOPSIS approach can simply be incorporated into a computer-based decision support system since it has simplicity in both computation and application.
First published online: 09 May 2017
This work is licensed under a Creative Commons Attribution 4.0 International License.
Antuchevičiene, J.; Zavadskas, E. K.; Zakarevičius, A. 2010. Multiple criteria construction management decisions considering relations between criteria, Technological and Economic Development of Economy 16(1): 109–125. https://doi.org/10.3846/tede.2010.07
Augerat, P.; Belenguer, J. M.; Benavent, E.; Corberán, A.; Naddef, D.; Rinaldi, G. 1998. Computational results with a branch and cut code for the capacitated vehicle routing problem. Research Report 949- M. Universite Joseph Fourier, Grenoble, France.
Backlund, P. B.; Shahan, D. W.; Seepersad, C. C. 2012. A comparative study of the scalability of alternative meta-modelling techniques, Engineering Optimization 44(7): 767–786. https://doi.org/10.1080/0305215X.2011.607817
Baldacci, R.; Hadjiconstantinou, E.; Mingozzi, A. 2004. An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Operations Research 52(5): 723–738. https://doi.org/10.1287/opre.1040.0111
Baldacci, R.; Toth, P.; Vigo, D. 2010. Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research 175(1): 213–245. https://doi.org/10.1007/s10479-009-0650-0
Ball, M. O. 2011. Heuristics based on mathematical programming, Surveys in Operations Research and Management Science 16(1): 21–38. https://doi.org/10.1016/j.sorms.2010.07.001
Bektas, T. 2006.The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega 34(3): 209–219. https://doi.org/10.1016/j.omega.2004.10.004
Bektas, T. 2012. Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing, European Journal of Operational Research 216(1): 83–93. https://doi.org/10.1016/j.ejor.2011.07.020
Bektas, T.; Erdoğan, G.; Ropke, S. 2011. Formulations and branch-and-cut algorithms for the generalized vehicle routing problem, Transportation Science 45(3): 299–316. https://doi.org/10.1287/trsc.1100.0352
Bell, J. E.; McMullen, P. R. 2004. Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics 18(1): 41–48. https://doi.org/10.1016/j.aei.2004.07.001
Belton, V.; Stewart, T. J. 2002. Multiple criteria decision analysis: an integrated approach. Boston: Kluwer Academic Publications. https://doi.org/10.1007/978-1-4615-1495-4
Chang, C. W.; Wu, C.-R.; Chen, H. C. 2008. Using expert technology to select unstable slicing machine to control wafer slicing quality via fuzzy AHP, Expert Systems with Applications 34(3): 2210–2220. https://doi.org/10.1016/j.eswa.2007.02.042
Chen, S. J.; Hwang, C. L. 1992. Lecture notes in economics and mathematical systems. Berlin, Germany: Springer.
Cordeau, J. F.; Laporte, G.; Savelsbergh, M. W. P.; Vigo, D. 2007. Vehicle routing, Chapter 6 in C. Barnhart, G. Laporte (Eds.). Handbooks in Operations Research and Management Science. Vol. 14. Amsterdam: North-Holland, 367–428.
Dagdeviren, M.; Yavuz, S.; Kılınc, N. 2009. Weapon selection using the AHP and TOPSIS methods under fuzzy environment, Expert Systems with Applications 36(4): 8143–8151. https://doi.org/10.1016/j.eswa.2008.10.016
Dantzig, G. B.; Ramser, J. H. 1959. The truck dispatching problem, Management Science 6(1): 80–91. https://doi.org/10.1287/mnsc.6.1.80
Dobson, D. C. 2003. Mathematical Modeling Lecture Notes [online], [cited 7 January 2003]. Available from Internet: http://www.math.utah.edu/~dobson/teach/540/notes.pdf
Dominguez, O.; Juan, A. A.; Barrios, B.; Faulin, J; Agustin, A. 2016. Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet, Annals of Operations Research 236(2): 383–404. https://doi.org/10.1007/s10479-014-1551-4
Ebadi, A.; Moslehi, G. 2012. Mathematical models for preemptive shop scheduling problems, Computers and Operations Research 39(7): 1605–1614. https://doi.org/10.1016/j.cor.2011.09.013
Ecer, F. 2014. A hybrid banking websites quality evaluation model using AHP and COPRAS-G: a Turkey case, Technological and Economic Development of Economy 20(4): 758–782. https://doi.org/10.3846/20294913.2014.915596
Eksioglu, B.; Vural, A. V.; Reisman, A. 2009. The vehicle routing problem: a taxonomic review, Computers and Industrial Engineering 57(4): 1472–1483. https://doi.org/10.1016/j.cie.2009.05.009
Expósito-Izquierdo, C.; Rossi, A.; Sevaux, M. 2016. A two-level solution approach to solve the clustered capacitated vehicle routing problem, Computers and Industrial Engineering 91: 274–289. https://doi.org/10.1016/j.cie.2015.11.022
Ezzatneshan, A. 2010. A algorithm for the vehicle problem, International Journal of Advanced Robotic Systems 7(2): 125–132. https://doi.org/10.5772/9698
Faulin, J.; Juan, A. A. 2008. The ALGACEA-1 method for the capacitated vehicle routing problem, International Transactions in Operational Research 15(5): 599–621. https://doi.org/10.1111/j.1475-3995.2008.00640.x
Gendreau, M.; Laporte, G.; Potvin, J.-Y. 2002. Metaheuristics for the Capacitated VRP, in P. Toth, D. Vigo (Eds.). SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM, 129–154. https://doi.org/10.1137/1.9780898718515.ch6
Gouveia, L.; VoB, S. 1995. A classification of formulations for the (time-dependent) traveling salesman problem, European Journal of Operational Research 83(1): 69–82. https://doi.org/10.1016/0377-2217(93)E0238-S
Hacioglu, U.; Dincer, H. 2015. A comparative performance evaluation on bipolar risks in emerging capital markets using fuzzy AHP-TOPSIS and VIKOR approaches, Inzinerine Ekonomika-Engineering Economics 26(2): 118–129. https://doi.org/10.5755/j01.ee.26.2.3591
Haimovich, M.; Kan, A. H. G. R.; Stougie, L. 1988. Vehicle routing, methods and studies. Analysis of Heuristics for Vehicle Routing Problems, 47–61.
Ivlev, I.; Kneppo, P.; Bartak, M. 2014. Multicriteria decision analysis: a multifaceted approach to medical equipment management, Technological and Economic Development of Economy 20(3): 576–589. https://doi.org/10.3846/20294913.2014.943333
Ji, P.; Chen, K. 2007. The vehicle routing problem: the case of the Hong Kong postal service, Transportation Planning and Technology 30(2–3): 167–182. https://doi.org/10.1080/03081060701390841
Kabak, M.; Dağdeviren, M. 2014. A hybrid MCDM approach to assess the sustainability of students’ preferences for university selection, Technological and Economic Development of Economy 20(3): 391–418. https://doi.org/10.3846/20294913.2014.883340
Kara, I.; Bektas, T. 2005. Minimal load constrained vehicle routing problems, in V. S. Sunderam, G. D. van Albada, P. M. A. Sloot, J. J. Dongarra (Eds.). Computational Science – ICCS 2005. ICCS 2005. Lecture Notes in Computer Science. Vol 3514. Berlin Heidelberg: Springer-Verlag, 188–195. https://doi.org/10.1007/11428831_24
Kara, I.; Derya, T. 2011. Polynomial size formulations for the distance and capacity constrained vehicle routing problem, in Numerical Analysis and Applied Mathematics ICNAAM 2011 AIP Conference Proceedings 1389, 19–25 September 2011, Halkidiki, Greece, 1713–1718.
Khandekar, A.; Antuchevičienė, V. J.; Chakraborty, S. 2015. Small hydro-power plant project selection using fuzzy axiomatic design principles, Technological and Economic Development of Economy 21(5): 756–772. https://doi.org/10.3846/20294913.2015.1056282
Kou, G.; Peng, Y.; Lu, C. 2014. MCDM approach to evaluating bank loan default models, Technological and Economic Development of Economy 20(2): 292–311. https://doi.org/10.3846/20294913.2014.913275
Kulkarni, R. V.; Bhave, P. R. 1985. Integer programming formulations of vehicle routing problems, European Journal of Operational Research 20(1): 58–67. https://doi.org/10.1016/0377-2217(85)90284-X
Laporte, G.; Nobert, Y. 1987. Exact algorithms for the vehicle routing problem, Annals of Discrete Mathematics 31: 147–184. https://doi.org/10.1016/s0304-0208(08)73235-3
Laporte, G.; Semet, F. 2002. Classical Heuristics for the Capacitated VRP, in P. Toth, D. Vigo (Eds.). SIAM monographs on discrete mathematics and applications. Vol. 9. The vehicle routing problem. Philadelphia: SIAM, 109–128.
Liu, P. 2009. Multi‐attribute decision‐making method research based on interval vague set and TOPSIS method, Technological and Economic Development of Economy 15(3): 453–463. https://doi.org/10.3846/1392-8619.2009.15.453-463
Luss, H.; Rosenwein, M. B. 1997. Operations research applications: opportunities and accomplishments, European Journal of Operational Research 97(2): 220–244. https://doi.org/10.1016/S0377-2217(96)00194-4
Maimoun, M.; Madani, K.; Reinhart, D. 2016. Multi-level multi-criteria analysis of alternative fuels for waste collection vehicles in the United States, Science of the Total Environment 550: 349–361. https://doi.org/10.1016/j.scitotenv.2015.12.154
Mandic, K.; Delibasic, B.; Knezevic, S.; Benkovic, S. 2014. Analysis of the financial parameters of Serbian banks through the application of the fuzzy AHP and TOPSIS methods, Economic Modelling 43: 30–37. https://doi.org/10.1016/j.econmod.2014.07.036
Mergias, I.; Moustakas, K.; Papadopoulos, A.; Loizidou, M. 2007. Multi-criteria decision aid approach for the selection of the best compromise management scheme for ELVs: the case of Cyprus, Journal of Hazardous Materials 147(3): 706–717. https://doi.org/10.1016/j.jhazmat.2007.01.071
Miller, G. A. 1956. The magic number seven plus or minus two, Psychological Review 63(2): 81–97. https://doi.org/10.1037/h0043158
Moghadam, B. F.; Sadjadi, S. J.; Seyedhosseini, S. M. 2010. Comparing mathematical and heuristic methods for robust vehicle routing problem, International Journal of Research and Reviews in Applied Sciences 2(2): 108–116.
Munoz, A. A.; Sheng, P. 1995. An analytical approach for determining the environmental impact of machining processes, Journal of Materials Processing Technology 53(3–4): 736–758. https://doi.org/10.1016/0924-0136(94)01764-R
Myronidis, D.; Papageorgiou, C.; Theophanous, S. 2016. Landslide susceptibility mapping based on landslide history and analytic hierarchy process (AHP), Nat Hazards 81(1): 245–263. https://doi.org/10.1007/s11069-015-2075-1
Nelson, C. A. 1986. A scoring model for flexible manufacturing system project selection, European Journal of Operational Research 24(3): 346–359. https://doi.org/10.1016/0377-2217(86)90028-7
Öncan, T.; Altınel, I. K.; Laporte, G. 2009. A comparative analysis of several asymmetric traveling salesman problem formulations, Computers and Operations Research 36(3): 637–654. https://doi.org/10.1016/j.cor.2007.11.008
Opasanon, S.; Lertsanti, P. 2013. Impact analysis of logistics facility relocation using the analytic hierarchy process (AHP), International Transactions in Operational Research 20(3): 325–339. https://doi.org/10.1111/itor.12002
Ordóñez, F.; Sungur, I.; Dessouky, M. 2008. A priori performance measures for arc-based formulations of vehicle routing problem, transportation research record, Journal of the Transportation Research Board 2032: 53–62. https://doi.org/10.3141/2032-07
Özgüven, C.; Özbakır, L.; Yavuz, Y. 2010. Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling 34(6): 1539–1548. https://doi.org/10.1016/j.apm.2009.09.002
Pannirselvam, G. P.; Ferguson, L. A.; Ash, R. C.; Siferd, S. P. 1999. Operations management research: an update for the 1990s, Journal of Operations Management 18(1): 95–112. https://doi.org/10.1016/S0272-6963(99)00009-1
Prakash, C.; Barua, M. K. 2015. Integration of AHP-TOPSIS method for prioritizing the solutions of reverse logistics adoption to overcome its barriers under fuzzy environment, Journal of Manufacturing Systems 37: 599–615. https://doi.org/10.1016/j.jmsy.2015.03.001
Robbins, S. P. 1994. Management. New Jersey, Prentice Hall.
Saaty, T. L. 1980. The Analytic Hierarchy Process. New York: McGraw-Hill.
Sarin, C. S.; Sherali, H. D.; Bhootra, A. 2005. New tighter polynomial length formulations for the asymmetric travelingsalesman problem with and without precedence constraints, Operations Research Letters 33(1): 62–70. https://doi.org/10.1016/j.orl.2004.03.007
Sen P.; Yang, J-B. 1998. Multiple criteria decision support in engineering design. London, Great Britain: Springer-Verlag London Limited. https://doi.org/10.1007/978-1-4471-3020-8
Singh, R. P.; Nachtnebel, H. P. 2016. Analytical hierarchy process (AHP) application for reinforcement of hydropower strategy in Nepal, Renewable and Sustainable Energy Reviews 55: 43–58. https://doi.org/10.1016/j.rser.2015.10.138
Soysal M.; Bloemhof-Ruwaard, J. M.; Bektaş, T. 2015. The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations, International Journal of Production Economics 164: 366–378. https://doi.org/10.1016/j.ijpe.2014.11.016
Stadtler, H. 1996. Mixed integer programming model formulations for dynamic multi-item multi-level capacitated lotsizing, European Journal of Operational Research 94(3): 561–581. https://doi.org/10.1016/0377-2217(95)00094-1
Tan, K. C.; Lee, L. H.; Zhu, Q. L.; Ou, K. 2001. Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering 15(3): 281–295. https://doi.org/10.1016/S0954-1810(01)00005-X
Toth, P.; Vigo, D. 2002. SIAM monographs on discrete mathematics and applications, Vol. 9, The Vehicle Routing Problem. Philadelphia: SIAM. https://doi.org/10.1137/1.9780898718515
Tsai, P.-H.; Chang, S.-C. 2013. Comparing the Apple iPad and non-Apple camp tablet PCs: a multicriteria decision analysis, Technological and Economic Development of Economy 19(sup1): 256–284. https://doi.org/10.3846/20294913.2013.881929
Vaidyanathan, B. S.; Matson, J. O.; Miller, D. M.; Matson, J. E. 1999. A capacitated vehicle routing problem for just-in- time, delivery, IIE Transactions 31(11): 1083–1092. https://doi.org/10.1080/07408179908969909
Vincke, P. 1992. Multicriteria decision aid. New York: Wiley.
Wang, T. C.; Chang, T. H. 2007. Application of TOPSIS in evaluating initial training aircraft under a fuzzy environment, Expert Systems with Applications 33(4): 870–880. https://doi.org/10.1016/j.eswa.2006.07.003
Wang, X.; Triantaphyllou, E. 2008. Ranking irregularities when evaluating alternatives by using some ELECTRE methods, OMEGA 36(1): 45–63. https://doi.org/10.1016/j.omega.2005.12.003
Water, C. D. J. 1988. Expanding the scope of linear programming solutions for vehicle scheduling problems, International Journal of Management Science 16(6): 577–583. https://doi.org/10.1016/0305-0483(88)90031-x
Wu, T.; Shi, L. 2011. Mathematical models for capacitated multi-level production planning problems with linked lot sizes, International Journal of Production Research 49(20): 6227–6247. https://doi.org/10.1080/00207543.2010.535043
Wu, T.; Shi, L.; Geunes, J.; Akartunalı, K. 2011. An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging, European Journal of Operational Research 214(2): 428–441. https://doi.org/10.1016/j.ejor.2011.04.029
Wu, T.; Shi, L.; Geunes, J.; Akartunalı, K. 2012. On the equivalence of strong formulations for ca¬pacitated multi-level lot sizing problems with setup times, Journal of Global Optimization 53(4): 615–639. https://doi.org/10.1007/s10898-011-9728-8
Yousefikhoshbakht, M.; Sedighpour, M. 2011. An optimization algorithm for the capacitated vehicle routing problem based on ant colony system, Australian Journal of Basic and Applied Sciences 5(12): 2729–2737.
Yurdakul, M.; İç, Y. T. 2005. Development of a performance measurement model for manufacturing companies using the AHP and TOPSIS approaches, International Journal of Production Research 43(21): 4609–4641. https://doi.org/10.1080/00207540500161746
Zeleny, M. 1982. Multiple Criteria Decision Making. New York: McGraw-Hill.