Research On Max-Min Ant System Algorithm In Solving SDVRP And SDWVRP

With the rapid development of economy in nowadays society, in order to achieve more and more economy benefits, enterprises not only put an eye on the product itself, but instead, more and more additional services are aroused to attract customers'attention. Transportation and logistics management services are flourishing under this background. Vehicle Routing Problem (VRP), as the key point of transportation and logistics management, is also major part of its research object. For traditional VRP, each customer has to be served by only one vehicle in total, which may conflict with the real transportation practice, where a customets. This motivates us to take split strategy in to consideration, called the Split-delivery Vehicle Routing Problem (SDVRP). However, in real-world cargo transportation practice, the cost is dependent not only on the distance traveled but also on the weight loaded, therefore, the solution we get from normal VRP may not be the most effective one. Thus, this paper proposes the split-delivery weighted vehicle routing problem (SDWVRP), which consists of constructing the optimal routes, with respect to the constraints on vehicle capacity and cargo weight, to serve a given set of customers with the minimum cost. Here, the "weight" is a general term that could be extended to represent the number or values of objects (cargo/goods/passenger) to be delivered or the importance/priority of customers (or points). Likewise, the terminology of "costs", apart from financial costs, also provides broad meanings-the minimum emission/petrol consumption when transporting general goods, the minimum risk of loss incurred when transporting perishable foods, livestock or dangerous goods, the maximum utility, degree of satisfaction, values or benefits to delivery customers, etc.Based on the background of logistics and distribution, this paper works on following major parts:Firstly, after looking deep into the background of SDVRP and its mathematical model, the paper has designed two related algorithms to solve the SDVRP problem, and the two algorithms are Max-Min Ant System Algorithm (MMAS) and Tabu Search Algorithm (TS), respectively. We have proved that MMAS algorithm is better in solving SDVRP, and the split strategy in SDVRP makes the model more effective than usual ones. The experimental data comes from standard VRP BENCHMARK instance bank. All the instances are classified into 7 different groups which are with diversified geographical distribution and weight distribution. Tests are implemented to figure out in which group of instance SDVRP presented to be the most effective. A full factorial experiment is also designed to find out the best MMAS algorithm parameter settings.Then based on the SDVRP model, considering the effect cargo weight has on route decision, we present a new model with cargo weight, called SDWVRP. Modified MMAS algorithm is proposed by taking the specific feature of the SDWVRP model into consideration. By comparing with SDVRP model, SDWVRP proved its effectiveness and feasibility in figuring out the best solution. When cargo weight varies largely and distribution scattered, the weighted model proved to be better in solution. By comparing with WVRP model, SDWVRP model proved its advantage in effectively reducing vehicle number and total cost in transportation by putting cargo weight into objective function. Large number of tests is implemented, and the benefits of split strategy are demonstated.All in all, the results of experiment have shown that diversified geographic and weight distribution do contribute to different results of SDWVRP models, that is to say, specific geographic and weight distribution will lead to fewer vehicle number and total transportation cost, therefore, helping to bring about more benefits to practical transportation activities accordingly.