Algoritmos para o problema de roteamento de veículos com coleta e entrega simultâneas

Abstract

In this work we deal with the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). This is a basic problem of the reverse logistic, defined as: Given a transportation network with $n$ customers and one depot, and each customer has a demand of pick-up and/or a demand of delivery, and a set of vehicles with limited capacity, the VRPSPD consists of defining optimized routes that satisfy all client demands and meet the capacity of the vehicles.Due to computational complexity of VRPSPD, the development and analysis of constructive heuristics is extremely important. This work compares five well known constructive heuristics at the literature and proposes three new heuristics. The results show that the proposed heuristics are better in 90% of the tested instances considering the travel distance reduction of the vehicles.The heuristic with better results at the literature (Insertion-BasedHeuristic) ie extend in two direction. Firstly, the alternative allowing toclose the current route earlier is considered. In the second direction, itis explored the use of a multicriteria decision aid tool to select the nodeto be inserted in the route in each step of the heuristic. The results showa significant travel distance improvement in 92% of instances.The four better heuristics showed in this work was applied in theconstruction phase of a GRASP based heuristic. This algorithm uses fourtypes of movements in the local search phase: interchange, reallocation,route elimination, crossover and 2Opt. The obtained results was compared with the better results in the literature. The solutions of the proposed heuristic reduced the total traveled distance significantly in 64% of instances. The results confirm that the application of good heuristics inthis phase improves the GRASP solution quality.