Getting Beyond the First Result of Solving a Vehicle Routing Problem
Pages 9 - 27
Abstract
The simple vehicle routing problem (VRP) is a common topic of discussion in introductory operations research/management science courses. The VRP can be framed in a variety of ways, and it can be difficult to solve to optimality. For solution purposes, introductory textbooks demonstrate how Excel’s Evolutionary Solver (ES) add-in produces a routing. The ES utilizes a genetic algorithm with a heuristic stopping rule to produce a routing that is not guaranteed to be optimal. Beyond pointing out that search controls, such as maximum execution time, may be extended and followed by restart(s) of ES, textbook treatments do not offer alternative ways to continue the search for a possibly better routing. In this paper, a suite of ways is presented in which students may investigate beyond what ES produces or any other optimality-uncertain VRP solution method. The suite includes perturbation methods and other ways that function within an Excel spreadsheet environment that is popular with students and textbook writers. Because there is no demonstrable feature that confirms optimality, the student problem Solver must settle for a ‘best found’ result as unsettling as it may be. The incertitude is addressed.
References
[1]
Anderson D, Sweeney D, Williams T, Camm J, Cochoran J, Fry M, Ohlmann J (2019) An Introduction to Management Science: Quantitative Approaches to Decision Making, 15th ed. (Cengage, Boston).
[2]
Augerat P, Belenguer J, Benavent E, Corberan A, Naddef D, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Universite Joseph Fourier, Grenoble, France.
[3]
Baker K, Camm J (2005) On the use of integer programming vs. evolutionary Solver in spreadsheet optimization. INFORMS Trans. Ed. 5(3):1–7.
[4]
Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Comput. Indust. Engrg. 99:300–313.
[5]
Carter A, Ragsdale C (2002) Scheduling newspaper advertising inserts using genetic algorithms. OMEGA: Internat. J. Management Sci. 30(6):415–421.
[6]
Drake M, Griffin M, Swann J (2011) Case article: Keeping logistics under wraps. INFORMS Trans. Ed. 11(2):57–62.
[7]
Eksioglu B, Vural A, Reisman A (2009) The vehicle routing problem: A taxonomic review. Comput. Indust. Engrg. 57(4):1472–1483.
[8]
Erdogan G (2017) An open source spreadsheet Solver for vehicle routing problems. Comput. Oper. Res. 87:62–72.
[9]
FrontlineSystems (2020) Accessed May 5, 2021, https://www.solver.com/excel-solver-evolutionary-solving-method-stopping-conditions.
[10]
Gutin G, Punnen A, eds. (2002) The Traveling Salesman Problem and Its Variations (Kluwer Academic Publishers, Dordrecht, Netherlands).
[11]
Hesse R, Scerno D (2009) How electronic spreadsheets changed the world. INFORMS J. Appl. Analytics 39(2):159–167.
[12]
Hillier F, Hillier M (2019) Introduction to Management Science: A Modelling and Case Studies Approach with Spreadsheet, 6th ed. (McGraw Hill Education, New York).
[13]
Hillier F, Lieberman G, Nag B, Basu P (2017) Introduction to Operations Research, 10th ed. (McGraw Hill Education, Noida, India).
[14]
Koksalan M, Salman F (2003) Beer in the classroom: A case study of location and distribution decisions. INFORMS Trans. Ed. 4(1):65–77.
[15]
Kulkarni R, Bhave P (1985) Integer programming formulations of vehicle routing problems. Eur.n J. Oper. Res. 20(1):58–67.
[16]
Laporte G (2009) Fifty years of vehicle routing. Transportation Sci. 43(4):408–416.
[17]
Mason A (2013) SolverStudio: A new tool for better optimisation and simulation modeling in excel. INFORMS Trans. Ed. 14(1):45–52.
[18]
Milburn A, Kirac E, Hadianniasar M (2017) Case article-growing pains: A case study of large-scale vehicle routing. INFORMS Trans. Ed. 17(2):75–80.
[19]
Pillac V, Gendreau M, Guéret C, Medaglia A (2013) A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225(1):1–11.
[20]
Pollaris H, Braekers K, Caris A, Janssens G, Limbourg S (2015) Vehicle routing problems with loading constraints: State-of-the art and future directions. OR Spectrum 37:297–330.
[21]
Ragsdale C (2001) Teaching management science with spreadsheets: From decision models to decision support. INFORMS Trans. Ed. 1(2):68–74.
[22]
Ragsdale C (2015) Spreadsheet Modeling and Decision Analysis, 7th ed. (South-Western Cengage Learning, Mason, OH).
[23]
Ragsdale C (2018) Spreadsheet Modeling and Decision Analysis: A Practical Introduction to Business Analytics, 8th ed. (South-Western Cengage Learning, Mason, OH).
[24]
Taja H (2018) Operations Research: An Introduction, 10th ed. (Pearson Education, Uttar Pradesh, India).
[25]
Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications, 2nd ed., MOS-SIAM Series on Optimization, vol. 18 (SIAM, Philadelphia).
[26]
Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing variants. Eur. J. Oper. Res. 286(2):401–416.
[27]
Winston W, Albright S (2009) Practical Management Science, rev. 3rd ed. (South-Western Cengage Learning, Mason, OH).
[28]
Winston W, Albright S (2012) Practical Management Science, 4th ed. (South-Western Cengage Learning, Mason, OH).
Index Terms
- Getting Beyond the First Result of Solving a Vehicle Routing Problem
Index terms have been assigned to the content through auto-classification.
Recommendations
Fifty Years of Vehicle Routing
The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title “The Truck Dispatching Problem.” The study of the VRP has given rise to major developments in the fields of exact algorithms and heuristics. In ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2021
64 pages
Copyright © 2021 The Author(s).
This work is licensed under a Creative Commons Attribution NonCommercial-NoDerivatives 4.0 International License. You are free to download this work and share with others, but cannot change in any way or use commercially without permission, and you must attribute this work as “INFORMS Transaction on Education. Copyright © 2021 The Author(s). https://doi.org/10.1287/ited.2021.0255, used under a Creative Commons Attribution License: https://creativecommons.org/licenses/by/4.0/creativecommons.org/licenses/by-nc-nd/4.0/.”
Publisher
INFORMS
Linthicum, MD, United States
Publication History
Published: 01 September 2021
Accepted: 02 March 2021
Received: 02 June 2020
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in