Design of Dynamic Vehicle Routing System

Design of Dynamic Vehicle Routing System

In traditional logistics distribution operation, vehicle routing plan is often made manually. However, when the number of customers and vehicles arise, transportation resources are usually utilized insufficiently. Therefore, an intelligent vehicle routing system will be very helpful to improve the distribution efficiency. Geographic information system (GIS) is a necessary part in a vehicle routing system. Two issues are essential for the development of a GIS system: map data sources and GIS developing platform. However, in China, the map data is too expensive, and also incompatible between different developing platforms. In addition, many GIS developing platforms like ArcGIS engine or MapX, are too specific and complex to use. Online map services can easily solve these problems: they share map data on the internet and provide developing APIs to public users for free. It's an alternative way to develop our own GIS application by using online map services. In real distribution process, customer orders emerge randomly.  

We need to plan our vehicle route dynamically to response these orders well. From this point of view, we need to know the real-time vehicle location and the real-time order status. Leveraged by the developing of GPS and wireless communication technology, we can now get real-time information easily. Based on the technologies mentioned above, this paper introduces a solution to develop dynamic vehicle routing system. After literature review, the principle of using online map service API is discussed and the detailed methods called in the vehicle routing system is reported. Then we explain the vehicle routing algorithm integrated in our system, which is called Variable Neighborhood Algorithm (VNS) algorithm. We also discuss the real-time requirements responding strategy and real-time traffic information handling strategy to draw real time distribution plan. After that, we report the design of this system, including data model design, system architecture design and system function design. 

A. Vehicle routing system The early studies on vehicle routing system choose the developing platforms offered by the professional GIS enterprises, such as ArcGIS, Mapinfo Professional, MapX and so on. HUO (2003) proposed a mathematics model of vehicle routing problem [1]. In this study, the authors use MapInfo Professional to partition the distribution region and then route each group individually. YANG (2010) combined GIS with logistics distribution technologies and developed a system by ArcGIS Engine [2].

B. Dynamic & Larger Scale Vehicle Routing Problem More and more attention has been paid to Dynamic Vehicle Routing Problem (DVRP) since the 1990s [3-4]. Different from static vehicle routing problem, dynamic vehicle routing problem considers uncertain information, including real-time service requests, time-dependent travel time between demand nodes and real-time vehicle control. In vehicle routing system, there is a clear need to develop solution procedures that are able to solve the large scale problems. https://codeshoppy.com/ For large scale problems, most VRP algorithms such as the well-known Clarke-Wright savings heuristics (Clark and Wright, 1964) [5] do not yield satisfying results within a reasonable amount of computation time. For the instance with 2400 uniformly distributed customers, for example, the Clarke­Wright savings heuristics would take several tens of hours to fmd the solution(Ouyang, 2007)[6]. Gehring et al. (1999) proposed standard benchmark problems of 1,000 customers. After that, much more research has been devoted to solve VRPs with up to 1,000 customers with various heuristics. These approaches to solve large-scale VRPTW can be categorized into two types: those that are developed to improve traditional heuristics algorithms by performing relatively broader search and avoiding the shortcoming of falling into local optima (KytOjoki, et aI., 2007[7]; Dondo and Cerda, 2009)[9]), and those that are based on the cluster-fIrst and routing-second principle (Ouyang, 2007)[6], which aims at reducing the problem size and computational time. Variable neighborhood search (VNS) was fIrst proposed by Mladenovic(1997) [10] and Hansen (1997)[11]. As a local search based metaheuristic, VNS behaves excellently in solving NP­hard problems. During the past few years, the VNS approach has been applied to variants of the VRPs effIciently. Kytojoki et al. (2007) presented an effIcient VNS heuristic, which is specifIcally aimed at solving very large scale real-life vehicle routing problems [7]. Polacek et ai. (2004) proposed a VNS heuristic to tackle the basic capacitated vehicle routing problem (CVRP) and achieved new best solutions in 71 cases [12].  Click Here