Research Of Cash Vehicle Routing Problem Based On GIS

Cash vehicle routing problem is an actual application of vehicle routing problem (VRP).Rational management and planning for cash vehicle routing, which is an effective mean toreduce the cost and enhance the work efficiency and safety of the cash vehicle.In order to resolve the problems in cash transportation, such as high cost, unevenworkload of different routes, unsafety of some paths and so on, this thesis studies the cashvehicle routing problem and put forward the comprehensive optimization target and thesolving scheme of“first route partitioning, then path optimization”. The cash vehicle routepartitioning model and path optimization model are constructed respectively and the relevantimproved algorithmsare proposed in the thesis. Finally, a cash vehicle VRP system isdeveloped combined with geographic information system(GIS), and the usefulness andreliability of the system is verified by an application case.A group of new concepts are proposed in the thesis, such as the comprehensive indexworkload, comprehensive index workload balanced factor and the distance of real roadnetwork between network. Route partitioning model is constructed and the improved nearestneighbor algorithm is used to realize the route partitioning goal. The nearest neighboralgorithm is improved by increasing the network gathered degree and balancing the workloadof different routes. The improved algorithm is veritfied by a certain company’s actual data.Experiments indicate the superiority of the improved algorithm in task allocation, drivingdistance and service time.To realize the path optimization target, the concept of traffic clear coefficient and safetyfactor are proposed in the thesis, and the corresponding connotation and calculation methodare defined respectively. Then the path optimization model is constructed with the minimumcomprehensive evaluation value of total distance, service time and safety requirements.Considering the imfluence of traffic jam for route optimization, an improved ant colonyalgorithm is proposed. The traffic clear level is introduced into ant colony algorithm toimprove the state transition probability, and the global and local pheromone updatingmechanism are introduced to increase the convergence speed. The improved ant colonyalgorithm is applied to the actual banking cash transportation vehicle routing optimization.Experiment results show that the improved algorithm could accelerat the rate of convergenceof algorithm, and reduce the operation cost of the cash transportation averagely.Finally a cash vehicle VRP system is developed based on GIS. The system could realizthe solving scheme of“first route partitioning, then path optimization”, and the solutionresults could be expressed by the intuitive form of map, data sheets and reports. The system istested by a certain company’s task instance.