ABSTRACT
In China, thetobacco distribution is organized by fixed districts and routes with lowefficiency and high distribution cost due to its unbalanced workload. And,though the dynamic method adopting vehicle routing algorithms produces optimalroutes, the unstable routes increase the delivery time and managerial cost. Soit is urgent and feasible to break the fixed districts to provide periodicbalanced partitions for tobacco distribution. In this paper, a multi-criteriabalanced partition model is built, whose minimal objectives including totalnumber of tours in all districts, the travel distance and time of all tours,and the balance objectives include number of tours, total demand, travelingdistance and time of each district are considered. An immune co-evolutionaryalgorithm with two stages is designed to search the optimal balancedpartitions. In the first stage, the initial balanced partitions are produced. Inthe second stage, the clonal selection procedure, with partition proliferation,selection and elimination, and cooperative searching among districts, isadopted to achieve balanced partition. The experiments on Lenfen city in Chinaas a practical application reveal the efficiency of the proposed model and algorithm.First, the searching processes are analyzed by exploring the partitions andPareto partitions. Second, the evolutionary process of the algorithm is shownby the varying of the multiple objectives. Finally, three methods includingfixed districts and routes, dynamic VRP scheduling and periodic balancedpartition are compared to show the value of the study.
Keywords: distributionsystem, partition optimization, vehicle routing problem, immune co-evolutionaryalgorithm, Geographic Information System
1. Introduction
In China, most ofthe cities still adopt fixed districts and routes to organize the tobaccodistribution. The tobacco distribution is organized by the city tobaccocompanies. The distribution cycle is commonly five workdays in a week. Theregion of city is correspondingly divided into five districts. Every workday thedistribution center deals with one region. Although the old method which adoptsfixed districts is convenient and simple, the efficiency is low and thedistribution cost is high because of its unbalanced workload. It is urgent andfeasible to break the fixed districts by optimized partitioning methods.
Inlogistics system, partitioning is also a technique for vehicle routing problem(VRP) to choose targets for a single tour. A lot of attention is given to theproblem of determining efficient routes within a given district. However, more significantlong-term savings can be achieved if the borders of the districts are optimallydetermined. Though VRP is widely studied, in most case the studies are limitedto the theoretical routing under the parameters and the objectives. Inparticular, it is assumed that all parameters are given and the feasibility ofthe model and algorithm in fact depends on the objectives, such as the totalcost. And the VRP scheduling methods produce different routes passing though differentcustomers set for every execution. The “dynamic” scheduling is difficult foroperations which increases the cost to organize the transportation and deliveryprocess. Therefore, a periodic balanced partition should be a better choice forChinese tobacco companies. The balanced partition is based on the averagedemands from all detailers. For each district, delivery vehicles, distance andtime are minimized and balanced to achieve a balanced workload. And, thedistrict should be in a better geographical shape without overlap each other.
In this paper, the partitionbalancing problem in Chinese tobacco distribution is studied. The tobacco distribution problemwith Chinese specific characters is seldom studied before. The problem of partitionbalancing, especially in the context of Chinese tobacco market, is hardlyaddressed in the existing literatures. Here, we build amulti-criteria model and propose an immune co-evolutionary algorithm to search theoptimal partitions for tobacco distribution in China.
