Article Preview
Top1. Introduction
The Travelling Salesman Problem (TSP) is defined as a salesman that is required to visit “n” given cities just once, departing from a city or depot and returning to the same point (Lin, 1965). The concern is which of the possible routes is the shortest so the salesman can travel the least. For almost sixty years this problem has been approached from quite a large variety of methods (Ma, Yang, Hou, Tan, & Liu, 2007; Saji & Riffi, 2015; Ouaarab, Ahiod, & Yang, 2013). TSP has real applications in engineering problems as well; a good example is the Vehicle Routing Problem (VRP) that can be considered as form of TSP in which a vehicle is planned to visit a number of cities (Christofides, 1976).
Mathematically, the problem can be defined as a graph G = (V, A) where V = {1, …, n} is a set of vertices that represent cities or customers with the depot located in vertex 1, and A is a set of arcs. Every arc (i, j) i ≠ j is associated to an element in the distance symmetrical matrix C= (cij) (Laporte, 1992). The aim of the TSP is to minimise the total distance (or cost) covered by the salesman. Let xij (i ≠ j) be a binary variable equal to 1 if and only if the arc (i, j) appears in the optimal solution; therefore, the main objective of the TSP is to find the most optimal route to be followed (Laporte, 1992):
(1)The way to find the exact solution for the TSP is to calculate all the possible routes and get the best one (depending on the cost function). This can only be implemented if the number of cities or customers is very small. However, as the number of cities increases, the possibilities grow exponentially and the direct search method wouldn’t work. So, an advanced optimisation algorithm is needed to be implemented. Along the years, several approaches have been studied in order to solve this problem. One solution is the Nearest Neighbour algorithm that suggests travelling to the closest neighbour from the salesman’s current position, which is also named as the “greedy algorithm”. Although the process is fairly rapid, a visual analysis shows that the route is far to be optimal: the first distances will tend to be very small, while the last ones are often very large (Boone, Sathyan, & Cohen, 2015). A useful extension of the TSP is called Multiple Travelling Salesmen Problem (MTSP). An application of MTSP is in VRP where a number of vehicles visit all the given cities (target points). Nature has served as a window display for several algorithms to solve the TSP in its different variations and mobile robots path planning (Palmieri, Yang, Rango, & Marano, 2017; Chen, Kong, Fang, & Wu, 2011). Genetic Algorithm, Metal Annealing, Neural Networks, Tabu Search and Ant Colony are good examples for this.
A new application of the MTSP which is also considered in this study, is electric vehicle (EV) fleet management system (FMS). There are few studies in the literature focusing on this topic. In a study by Betz, Werner, & Lienkamp (2016), a mixed fleet of non-electric and electric vehicles was assessed. Then, a new model was developed to investigate the financial and ecological influences of replacing conventional vehicles with EVs to generate a personalized optimal fleet composition according to the number of trips and vehicle specifications. In a study by Hu, Morais, Sousa, and Lind (2016), a review of the optimization and control methods of intelligent EV fleet charging is discussed and the fleet operator services to other actors in a smart grid are presented. In a study by Chen, Kockelman, and Hanna (2016), operation of an autonomous EV fleet has been studied by doing simulations. The results have shown that the size of the fleet should be determined based on the charging infrastructure and vehicle range. In another study by Chao & Xiaohong (2013), differences between a fleet of electric buses and a fleet of diesel buses are assessed. It is shown that such differences need significant changes in vehicle scheduling methods when switching from diesel to electric.