Solving Mixed Capacitated General Routing Problem With Reduced Viterbi Searching Algorithm

Demand of tasks may distribute on crossroads or both sides of streets in the model of Mixed Capacitated General Routing Problem(MCGRP)which is NP-complete problem and has important research value.It has wide applications in real life such as urban waste collection,school bus transportation and street sweeping.Paper investigates MCGRP and two related variants.Tasks in Mixed Capacitated General Routing Problem with Time Windows(MCGRP-TW)needs to be satisfied within given time.Bi-objective Mixed Capacitated General Routing Problem(Bi-MCGRP)considers not only minimize total cost but load balance among different vehicles.MCGRP and its variants cannot be solved in polynomial time.For this reason,a Multiphase Local Search with Reduced Viterbi(RV-MLS)has been proposed.The paper has three main contributions: Three searching policy has been adopted to guide algorithm searching in the solution space generated by five operators Reduced Viterbi decoding procedure is used to determine the best serving direction of tasks locating on streets.Adjust RV-MLS with moderate modification,algorithm can be used to solve variants easily.The article conducts experiments on three types of problems.Five groups of 331 examples are selected for MCGRP.The results of 45 examples have been improved with average promotion of 0.91%,2 examples doesn’t reach the known optimal solution,but gaps are all within 0.2%.In MCGRP-TW,5 groups of 36 examples are selected,among which 4 examples are improved with average promotion of 0.76%,the gap between 1 example and the optimal solution was 0.01%.In Bi-MCGRP,three groups of 67 calculation examples are selected,and three different fitness functions are used to solve the approximate Pareto optimal boundary.It can be seen that the algorithm has great advantages in solution effect and scalability.