متاهیوریستیک ترکیبی برای مسیریابی مسائل وسیله نقلیه چند هدفه با پنجره های زمان

The Capacitated Vehicle Routing Problem with Time Windows is an important combinatorial optimization problem consisting in the determination of the set of routes of minimum distance to deliver goods, using a fleet of identical vehicles with restricted capacity, so that vehicles must visit customers within a time frame. A large number of algorithms have been proposed to solve single-objective formulations of this problem, including meta-heuristic approaches, which provide high quality solutions in reasonable runtimes. Nevertheless, in recent years some authors have analyzed multi-objective variants that consider additional objectives to the distance travelled. This paper considers not only the minimum distance required to deliver goods, but also the workload imbalance in terms of the distances travelled by the used vehicles and their loads. Thus, MMOEASA, a Pareto-based hybrid algorithm that combines evolutionary computation and simulated annealing, is here proposed and analyzed for solving these multi-objective formulations of the VRPTW. The results obtained when solving a subset of Solomon’s benchmark problems show the good performance of this hybrid approach.

The Vehicle Routing Problem (VRP), and its multiple variants, is a core problem in transportation, logistics, and supply chain management. Logistics, and especially the distribution of goods, lies at the heart of business activity because it is often coupled with inventory and production decisions, and the delivery cost accounts for a significant portion of the total logistic costs (Alabas-Uslu & Dengiz, 2011). Bearing in mind that problems in the domain of goods distribution can be viewed as a VRP (Mester & Bräysy, 2007), this problem contributes directly to reducing costs of all logistic systems (Alvarenga, Mateus, & de Tomic, 2007). Logistic managers need to make decisions to improve the design of their logistic systems, including appropriate decisions concerning the strategies to provide customers with their services while satisfying the company’s logistic priorities according to the available vehicle fleet. Furthermore, current concerns over global warming, resource depletion, and the social impact of traffic congestion and pollution are driving companies, governments, and researchers to improve the efficiency of logistics and distribution operations (Hosny & Mumford, 2010). VRPs are combinatorial optimization problems linked with many branches of mathematics, economics, computer science, and operations research. Since the family of vehicle routing problems is included in the category of NP-hard problems (Lenstra & Rinnooy Kan, 1981), they are hard to solve, especially when the number of customers is large (Lee, Lee, & Lin, 2008). The richness and difficulty of these problems has made vehicle routing an area of intense research work, as witnessed by the large number of research papers found in the literature (Eksioglu, Vural, & Reisman, 2009). Often, the number of customers combined with the complexity of real-life data does not permit them to be solved using exact methods, which is why current research concentrates on heuristic algorithms that are capable of finding high quality solutions to real-life problems in limited time. In particular, heuristics and meta-heuristics support managers in decision-making with approximate solutions to complex problems (Gendreau & Potvin, 2010). There are different variants of VRPs that aim to take into account the constraints and details of the problem, while also including different aspects of its nature, such as its dynamicity, time dependency, stochastic aspects, etc. An important variant of the VRP is the Capacitated Vehicle Routing Problem with (hard) Time Windows (VRPTW). It consists in determining the optimal set of routes of a fleet of identical vehicles with restricted capacity so that all customers, whose demands are known, are serviced exactly once within each time window. These time windows impose that the vehicle must begin the service to the customer within the time window defined by the earliest and latest times allowed by the customer for the start of service (El-Sherbeny, 2010). Routing problems are often set up with the single-objective of minimizing the cost of the solution despite the fact that the majority of the real applications associated with this problem are multi-objective in nature (Jozefowiez et al., 2008 and Dabia et al., 2013). This paper presents a new Pareto-based multi-objective approach that uses a multi-start simulated annealing strategy for solving a multi-objective formulation of the VRPTW that aims to minimize the total distance of the vehicles used to service the customers, while also minimizing the imbalance of workloads (distances travelled/goods delivered by the vehicles). This new approach is evaluated in comparison with two well-known multi-objective evolutionary algorithms, NSGA-II (Deb, Agrawal, Pratap, & Meyarivan, 2001) and SPEA2 (Zitzler, Laumanns, & Thiele, 2001). Section 2 describes the Capacitated Vehicle Routing Problem with Time Windows, while also justifying the importance of using multi-objective optimization methods to solve real-life routing problems. Section 3 details the multi-objective evolutionary algorithm proposed here, while the results obtained when solving some test problems are commented upon in Section 4. Finally, Section 5 provides the conclusions to this work.

Over the past decades, the design of methods to solve vehicle routing problems has been an area of research that has attracted much attention, due to its influence in transportation, logistics, and supply chain management. Often, the number of customers combined with the complexity of real-life data does not permit the problem to be solved exactly, and heuristic methods must therefore be applied. These include heuristic approaches, which provide approximate solutions in runtimes which are acceptable for transportation and logistic managers. This paper presents and analyzes a new Pareto-based hybrid meta-heuristic, MMOEASA, for solving multi-objective formulations of the VRPTW, here called WB-VRPTW, which considers not only the minimum distance required to deliver goods, but also the workload imbalance, in terms of distances travelled and loads transported by the vehicles. This hybrid approach combines evolutionary computation and simulated annealing in a multi-start manner with the aim of providing a set of non-dominated solutions which can be later analyzed by the decision maker according to particular criteria. The performance of this hybrid approach is compared with two popular multi-objective evolutionary algorithms, NSGA-II and SPEA2, when solving a some of the Solomon’s benchmark instances. The main contribution of this work is that the hybrid approach achieves highly competitive non-dominated fronts in terms of hyper-volume, set coverage, and spacing metrics, outperforming those obtained by NSGA-II and SPEA2. Furthermore, this research may prove useful to those researchers interested in solving multi-objective formulations of the vehicle routing problem and its variants, thus increasing the application of this problem to the real world.