We introduce the “Pollution Traveling Salesman Problem” (PTSP), a generalization of the well-known Traveling Salesman Problem which aims at finding a Hamiltonian tour that minimizes a function of fuel consumption (dependent on distance traveled, vehicle speed and vehicle load) and driver costs. We present a Mixed Integer Linear Programming (MILP) model for the PTSP, enhanced with subtour elimination constraints, and propose an Iterated Local Search (ILS) metaheuristic algorithm. The ILS algorithm first builds a feasible tour, based on the solution of the Linear Programming (LP) relaxation of the MILP model, and then loops between three phases: perturbation, local search and acceptance criterion. The results obtained by the ILS algorithm on instances with up to 50 customers are compared with those found by a Cut-and-Branch algorithm based on the enhanced MILP model. The results show the effectiveness of the ILS algorithm, which can find the best solution for about 99% of the instances within short computing times.
Keywords:
Pollution Traveling Salesman Problem, Iterated Local Search, MILP Model, Separation Procedures
Biographies
Paolo Toth is "Professor Emeritus" of “Operations Research” at DEI (Department of Electrical and Information Engineering “Guglielmo Marconi”), University of Bologna, where he was Full Professor from 1983 to 2011. His research interests include Operations Research and Mathematical Programming methodologies and, in particular, the design of exact and heuristic algorithms for the solution of Combinatorial Optimization problems. He is author of more than 180 papers published in international journals. He was President of EURO (Association of the European Operational Research Societies) for the period 1995-1996, and President of IFORS (International Federation of the Operational Research Societies) for the period 2001-2003. He received several international awards, among which: the "EURO Gold Medal" (the highest distinction within Operations Research in Europe) in 1998; the "Robert Herman Lifetime Achievement Award in Transportation Science" (from INFORMS) in 2005; the "INFORMS Fellowship" in 2016. In May 2003, the University of Montreal conferred him a "Doctorate honoris causa" in Operational Research.
Valentina Cacchiani is Senior Assistant Professor at the Department of Electrical and Information Engineering "Guglielmo Marconi" of the University of Bologna in the Operations Research Group. In 2014 she got the Italian academic qualification for Associate Professor and in 2018 for Full Professor in Operations Research. She has 30 publications in International Journals such as Mathematical Programming, Transportation Science, European Journal of Operational Research, Transportation Research Part B and Computers & Operations Research. Since 2003 she has been involved in several European and National Projects. She has several collaborations with research groups in Europe and has given seminars in several universities. Her scientific interests are mainly related to Combinatorial Optimization Problems arising in real-world applications.
Carlos Contreras-Bolton received his BSc degree in Computer Science in 2010 and his MSc degree in Computer Science Engineering in 2013, both from the University of Santiago of Chile. Currently he is a PhD student in Biomedical, Electrical and System Engineering at the University of Bologna, Italy. His current research interests are on exact and heuristic methods to solve combinatorial optimization problems.
John Willmer Escobar currently works at the Pontificia Universidad Javeriana of Cali (Colombia), at the Department of Civil and Industrial Engineering as a full-time Associate Professor, and at the Department of Accounting and Finance as a Part-time Professor. His research interests include Industrial Engineering, Theory of Computation and Computing in Mathematics, Natural Science, Engineering, Logistics, and Financial Risk.
Luis Miguel Escobar-Falcón obtained a degree in Computer Science Engineering (2007) and a M.Sc. degree in Electrical Engineering (2012) at the Technological University of Pereira, Colombia, where he is a Ph.D. student in Engineering. He has also performed research activities abroad at the University of Bio-Bio (Chile) and at the University of Bologna (Italy). He is currently the Research Coordinator of Integra S.A, operator of the Bus Rapid Transit System of Pereira. His research interests include the design and implementation of algorithms for the solutions of Operations Research problems such as Packing Problems, Vehicle Routing Problems and Scheduling Problems.
Rodrigo Linfati is an Assistant Professor of Industrial Engineering at the University of Bío-Bío (Chile). He received a PhD degree in Operational Research from the University of Bologna (Italy). His current research interests include the design of math0ematical models and the development of effective (meta-)heuristic algorithms for the solution of combinatorial optimization problems.