A Bi-Modal Routing Problem with Cyclical and One-Way Trips: Formulation and Heuristic Solution
Abstract
A bi-modal routing problem is solved using a heuristic approach. Motivated by a recreational hiking application, the problem is similar to routing problems in business with two transport modes. The problem decomposes into a set covering problem (SCP) and an asymmetric traveling salesperson problem (ATSP), corresponding to a hiking time objective and a driving distance objective. The solution algorithm considers hiking time first, but finds all alternate optimal solutions, as inputs to the driving distance problem. Results show the trade-offs between the two objectives.
Keywords: |
Heuristic; mountaineering; optimization; operations research; vehicle routing
|
Full Text: |
References
S. D. Smith and M. Dickerman, Eds., “AMC White Mountain Guide with Maps,” in The Appalachian Mountain Club, 29th edition, 2012.
N. Jozefowiez, F. Semet and E. G. Talbi, “Multi-Objective Vehicle Routing Problems,” European Journal of Operational Research, vol. 189, no. 2, 293–309, 2008.
G. Gutin, Ed., The Traveling Salesman Problem and Its Variations. Springer, 2007.
D. L. Applegate, R. E. Bixby, V. Chvatal, W. J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007.
B. Golden, S. Raghavan, and E. Wasil, Eds., “The Vehicle Routing Problem: Latest Advances and New Challenges,” Operations Research/Computer Science Interfaces, 2008. https://doi.org/10.1007/978-0-387-77778-8
M. Dror, Ed., Arc Routing: Theory and Solutions. Springer, 2000.
K. Braekers, K. Ramaekers and I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,” Computers & Industrial Engineering, vol. 99, pp. 300–313, Sep. 2016.
https://doi.org/10.1016/j.cie.2015.12.007
J. R. Current and D. A. Schilling, “The Covering Salesman Problem,” Transportation Science, vol. 23, no. 3, pp. 208–213, Aug. 1989. https://doi.org/10.1287/trsc.23.3.208
M. Gendreau, G. Laporte, and F. Semet, “The Covering Tour Problem,” Operations Research, vol. 45, no. 4, pp. 568–576, Aug. 1997. https://doi.org/10.1287/opre.45.4.568
N. Jozefowiez, F. Semet, and E.-G. Talbi, “The bi-objective covering tour problem,” Computers & Operations Research, vol. 34, no. 7, pp. 1929– 1942, Jul. 2007. https://doi.org/10.1016/j.cor.2005.07.022
M. Fischetti and P. Toth, “An Additive Approach for the Optimal Solution of the Prize-Collecting Traveling Salesman Problem,” in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad Eds. Amsterdam: North-Holland, pp. 319–343, 1988.
E. Balas, “The prize collecting traveling salesman problem,” Networks, vol. 19, no. 6, pp. 621–636, Oct. 1989. https://doi.org/10.1002/net.3230190602
B. L. Golden, L. Levy and R. Vohra, “The Orienteering Problem,” Naval Research Logistics, vol. 34, 307–318, 1987.
https://doi.org/10.1002/1520-6750(198706)34:3<307::aid- nav3220340302>3.0.co;2-d
R. Ramesh, Y.-S. Yoon, and M. H. Karwan, “An Optimal Algorithm for the Orienteering Tour Problem,” ORSA Journal on Computing, vol. 4, no. 2, pp. 155–165, May 1992. https://doi.org/10.1287/ijoc.4.2.155
L. Levy and L. Bodin., “Scheduling the Postal Carriers for the United States Postal Service: An Application of Arc Partitioning and Routing,” in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad Eds. Amsterdam: North-Holland, pp. 359–394, 1988.
E. Gussmagg-Pfliegl, F. Tricoire, K. F. Doernery, R. F. “Hartl, Mail- Delivery Problems with Park-and-Loop Tours: A Heuristic Approach” in ORP3 Meeting, Cadiz. September 13–17, 2011.
A. Černá, J. Černý, F. Malucelli, M. Nonato, L. Polena, and A. Giovannini, “Designing Optimal Routes for Cycle-tourists,” Transportation Research Procedia, vol. 3, pp. 856–865, 2014. https://doi.org/10.1016/j.trpro.2014.10.064
D. Gavalas, C. Konstantopoulos, K. Mastakas, and G. Pantziou, “A survey on algorithmic approaches for solving tourist trip design problems,” Journal of Heuristics, vol. 20, no. 3, pp. 291–328, Mar. 2014. https://doi.org/10.1007/s10732-014-9242-5
Refbacks
- There are currently no refbacks.
Copyright (c) 2017 Roger B. Grinde
This work is licensed under a Creative Commons Attribution 4.0 International License.