Formulation And Ant Colony Optimization For Weighted Vehicle Routing Problems

The vehicle routing problems are well-known operations research models for a class of transportation and logistics management. The objective of the most VRP models makes only approximate descriptions of practical problems and neglects the effect of cargo weight on the total costs; as a result, the optimal routes may not be the minimum cost one. To address this case, the quantity loaded in the vehicle should be considered as a part of the objective when optimizing the vehicle routine, rather than as a constant from a customer to another in a routine. This motivates us to consider a new type of VRP on the background of a toll-by-weigth scheme for China Expressway and lower carbon emission obligation policy with consideration of loading cost, which are weighted single vehicle routing problem, weighted vehicle routing problem, spilt delivery weighted vehicle routing problem and design corresponding algorithms. The ’weight’ is not only in terms of quantity, but also represents the values of goods, importance/priority of customers; and correspondingly, the objective ’cost’ has as well broad meaning. Apart from the costs itself, it may represent the emission/petrol consumption, risk of loss during the transportation, maximum utility, satisfaction degree, values or benefits of delivering customers.Based on the background of logistics and distribution, this research investigates into modeling and algorithms on weighted vehicle routing problems by adopting the theory and method of the optimization. The major work of this paper includes servel aspects as follows: this paper investgates into weighted single vehicle routing problem (WSVRP) on the background and formulation, proposes a mutated max-min ant conlny algorithm and analyzes necessity of WSVRP model, the effect of varying the parameters of weight-related cost on the total cost and transform M-MMAS to solve instances of TSP Benchmark to verify the validity of the algorithm.Secondly, weighted vehicle routing problem (WVRP) is modeling by taking the vehicle capacity constraints into consideration based on WSVRP. The detailed description of the background of the weighted vehicle routing problem (WVRP) has been given and the mathematical model of WVRP is presented. Beam-MMAS algorithm is designed for solving WVRP by considering the characteristic of the problem. The VRP Benchmark instances are classified from points’ distribution and weigth features. Experiments of seven types of instances are carried to explain effectiveness of WVRP model. Comparisons between costs of WVRP and the shortest routes under different weight features and similar customer distributions and different customer distributions with similar weight features are shown to discuss applicability of WVRP. The full factorial experiment is designed to determine how to set the Beam-MMAS algorithm parameters. The performance of the algorithm is also studied by comparing with other algorithms for the same problem.Finally, based on WVRP model, spilt delivery vehicle routing problem (SDWVRP) is proposed that considers customer demand is allowed to be split. Max-Min ant system algorithm is designed to solve SDWVRP. Comparisons of SDWVRP model and SDVRP model is to discuss the significance of considering weight in the formulation.305instances are designed to make comparisons between SDWVRP model and WVRP model from used vehicles and total costs in order to analyze advantage of the customer demand can be split and the factors influence the advantage.The experiments and analysis can be concluded that in some specific customer demand and customer position distribution, it can bring potential profits and save transportation cost by considering the weight and the spit of the customer demand. When the weight of customers has large deviation and customers with scattered position distribution, it’s more necessary to consider the weighting factor in the formulation which can bring more cost savings. The delivery cost reductions when customer demand is allowed to be split attribute to reduce the number of used vehicles. On case that the average of customer weight is greater than half the vehicle capacity but less than three quarters of the vehicle capacity and the weight variance is relatively small, the largest cost savings are obtained.