A comparative study of the capability of alternative mixed integer programming formulations

    Baris Kececi Affiliation
    ; Tusan Derya Affiliation
    ; Esra Dinler Affiliation
    ; Yusuf Tansel Ic Affiliation


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 formula­tion. 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

Keyword : capacitated vehicle routing problem, AHP, TOPSIS, multi-criteria analysis, optimization, operations research, mathematical model

How to Cite
Kececi, B., Derya, T., Dinler, E., & Ic, Y. T. (2018). A comparative study of the capability of alternative mixed integer programming formulations. Technological and Economic Development of Economy, 24(2), 561–584.
Published in Issue
Mar 20, 2018
Abstract Views
PDF Downloads
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.


Ali, O.; Verlinden, B.; Oudheusden, D. V. 2009. Infield logistics planning for crop-harvesting operations, Engineering Optimization 41(2): 183–197.

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.

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.

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.

Baldacci, R.; Toth, P.; Vigo, D. 2010. Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research 175(1): 213–245.

Ball, M. O. 2011. Heuristics based on mathematical programming, Surveys in Operations Research and Management Science 16(1): 21–38.

Bektas, T. 2006.The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega 34(3): 209–219.

Bektas, T. 2012. Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing, European Journal of Operational Research 216(1): 83–93.

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.

Bell, J. E.; McMullen, P. R. 2004. Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics 18(1): 41–48.

Belton, V.; Stewart, T. J. 2002. Multiple criteria decision analysis: an integrated approach. Boston: Kluwer Academic Publications.

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.

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.

Dantzig, G. B.; Ramser, J. H. 1959. The truck dispatching problem, Management Science 6(1): 80–91.

Dobson, D. C. 2003. Mathematical Modeling Lecture Notes [online], [cited 7 January 2003]. Available from Internet:

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.

Ebadi, A.; Moslehi, G. 2012. Mathematical models for preemptive shop scheduling problems, Computers and Operations Research 39(7): 1605–1614.

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.

Eksioglu, B.; Vural, A. V.; Reisman, A. 2009. The vehicle routing problem: a taxonomic review, Computers and Industrial Engineering 57(4): 1472–1483.

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.

Ezzatneshan, A. 2010. A algorithm for the vehicle problem, International Journal of Advanced Robotic Systems 7(2): 125–132.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Kulkarni, R. V.; Bhave, P. R. 1985. Integer programming formulations of vehicle routing problems, European Journal of Operational Research 20(1): 58–67.

Laporte, G.; Nobert, Y. 1987. Exact algorithms for the vehicle routing problem, Annals of Discrete Mathematics 31: 147–184.

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.

Luss, H.; Rosenwein, M. B. 1997. Operations research applications: opportunities and accomplishments, European Journal of Operational Research 97(2): 220–244.

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.

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.

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.

Miller, G. A. 1956. The magic number seven plus or minus two, Psychological Review 63(2): 81–97.

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.

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.

Nelson, C. A. 1986. A scoring model for flexible manufacturing system project selection, European Journal of Operational Research 24(3): 346–359.

Ö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.

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.

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.

Ö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.

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.

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.

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.

Sen P.; Yang, J-B. 1998. Multiple criteria decision support in engineering design. London, Great Britain: Springer-Verlag London Limited.

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.

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.

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.

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.

Toth, P.; Vigo, D. 2002. SIAM monographs on discrete mathematics and applications, Vol. 9, The Vehicle Routing Problem. Philadelphia: SIAM.

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.

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.

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.

Wang, X.; Triantaphyllou, E. 2008. Ranking irregularities when evaluating alternatives by using some ELECTRE methods, OMEGA 36(1): 45–63.

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.

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.

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.

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.

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.

Zeleny, M. 1982. Multiple Criteria Decision Making. New York: McGraw-Hill.