Research On Multi-depot Arc-node Routing Problem In The Rescue Of Breakdown Vehicles

It is generally assumed that the vehicle may depart from the depot and service all the arc customers within certain rules,then return back to the depot in a capacitated arc routing problem.However,there are two types of consumers in a breakdown vehicle rescue problem.The node customer only needs service like oil and electricity service without vehicle's movement.The arc customer needs service of breakdown vehicle's movement from breakdown location to maintenance location in time.Aiming at the problem,this paper presents a multi-depot arc-node routing problem in the rescue of breakdown vehicles,in which each rescue vehicle should provide corresponding services to all customers before their respective respond-time and return back to the depot.The objective is to find a set of routes with minimized cost under the max duration constraints of the vehicles.A firefly algorithm(FA)is proposed to solve this NP-hard problem in this paper.Firstly,an improved saving algorithm based on gamble roulette algorithm is used to generate the initial solution set.Secondly,characteristic values of the population are defined in order to calculate step length.Finally,a greedy remove-insert method is applied for local search to enhance and update the quality of less light intensity solution and achieve the most optimal solution.FA has been validated in the test instances by comparing with the results performed by CPLEX.The test instances are obtained by the modification of classical instances in pickup and delivery problem(PDP).The results of a greedy remove-insert method and CPLEX within 2 hours' calculation are respectively compared with the result of FA to prove the effectiveness of the algorithm.As a result in medium scale instance,the quality of solution performed by FA is better by averagely 6.57%than greedy remove-insert method and better by 6.69%than CPLEX.The standard deviation of our results is around 20,which shows great stability of FA.The average computational time of FA is 20.23 minutes which is much lower than the 2 hours of CPLEX results.The proposed algorithm offers the decision-making support for vehicle rescue enterprise and enables them to reduce operating costs and improve rescue efficiency without compromising customer satisfaction.