A Mathematical Model for Pollution Travelling Salesman Problem

Authors

  • Supakrit Nanasilp Department of Industrial Engineering, Faculty of Engineering, Chiang Mai University
  • Warisa Wisittipanich Department of Industrial Engineering, Faculty of Engineering, Chiang Mai University

Keywords:

Pollution Travelling Salesman Problem, Mathematical Model, Travelling Salesman Problem, Minimization of Fuel Consumption

Abstract

This paper studies Pollution Travelling Salesman Problem (PTSP). PTSP is a generalization of the well-known Travelling Salesman Problem (PTSP) which aims to find a suitable tour that minimizes fuel consumption in liters. This paper presents a mixed integer linear programming (MILP) for Pollution Travelling Salesman Problem which its objective function considers fuel consumption in term of vehicle engine efficiency, transmission, vehicle load, vehicle speed, road angle, distance and driver wages. The decision variables of the problem include routing of a vehicle, vehicle load and speed level. In this study, the PTSP is solved by the exact algorithm with optimization solver. The experiment uses 15 generated instances with the number of cities varying from 5 to 20 cities. The numerical results obtained by LINGO show that, in small-size instances, optimal solutions are easily found within fast computing time. When the number of cities increases to 15 cities, the model takes 3 to 8 hours to find optimal solutions. Finally, when the number of cities increases to 20 cities, the model cannot find optimal solution within acceptable computing time of 10 hours.

Downloads

Download data is not yet available.

References

Reference
[1] ม. ส. ปริมณภา จงจิตรกลาง, ปวิตรา สายจริงวงศ์, สาวรส จั่นขุนทด, ลักษณา วรศศิกุล, ธวัช ชาวัน, และอื่นๆ. (2019, 11 เมษายน). สาเหตุและผลกระทบของมลพิษทางอากาศ. Available: http://www.rmuti.ac.th/user/thanyaphak/Web%20EMR/Web%20IS%20Environmen%20gr.4/Mola2.html

[2] W. Cook. (Mar 10). History of the tsp. Available: www.math.uwaterloo.ca/tsp/history/index.html

[3] V. V. Burkhovetskiy and B. Y. Steinberg, "Parallelizing an exact algorithm for the traveling salesman problem," Procedia Computer Science, vol. 119, pp. 97-102, 2017/01/01/ 2017.

[4] J. Kinable, B. Smeulders, E. Delcour, and F. C. R. Spieksma, "Exact algorithms for the Equitable Traveling Salesman Problem," European Journal of Operational Research, vol. 261, pp. 475-485, 2017/09/01/ 2017.

[5] W. D. C. Franz Josef Ahlers, Claudio Fleiner, Lester Godwin, Mikal Keenan, Rituraj Deb Nath, et al. (2013, Mar 10). Differential Evolution (DE). Available: http://www1.icsi.berkeley.edu/~storn/code.html#basi

[6] X. Wang and G. Xu, "Hybrid Differential Evolution Algorithm for Traveling Salesman Problem," Procedia Engineering, vol. 15, pp. 2716-2720, 2011/01/01/ 2011.

[7] V. Cacchiani, C. Contreras Bolton, J. Escobar, L. M. Escobar Falcón, R. Linfati, and P. Toth, "An Iterated Local Search Algorithm for the Pollution Traveling Salesman Problem," ed, 2018, pp. 83-91.

Downloads

Published

2020-06-02