Spreadsheet-Based Modeling and Optimization of a Bi-Modal Traveling Salesman Problem: Model, Solution, and Case
Roger B. Grinde · DOAJ (DOAJ: Directory of Open Access Journals) · 2020
This paper presents a bi-modal routing problem and two-phase spreadsheet-based model and solution approach. The problem is the Bi-Modal Covering Salesman Problem, and the context for the problem in this paper is a recreational hiking problem. Two hikers seek to traverse a set of peaks, where they have defined a number of hikes from which to choose. The problem is to a) identify the set of hikes in order to minimize a hiking time objective while ascending all peaks, followed by b) sequencing the chosen hikes in order to minimize a driving distance objective. The problem essentially combines two well-known problems in Operations Research: the Set Covering Problem and the Traveling Salesman Problem. A mathematical programming formulation is presented, followed by a detailed explanation of the Excel™ model and solution approach with Solver™, using linear and evolutionary engines. The model is enhanced using Visual Basic for Applications. In instruction, it can be utilized in many ways, from a classroom discussion example all the way up to a semester long project done in several phases. A case, split into two parts, is provided in the appendix. The full workbook and a template file is available upon request from the author.