Optimization of Express Delivery Routing Problem

Headnote

Abstract

In this research, we describe some key issues of distribution route optimization with express large data. It includes data warehouse establishment for storing user and map information, establishment of the real distribution network topology, establishment of the algorithm and model of the recommended delivery route, development of the visualization tools with the help of GIS tools to form the regional operation board. This paper aims to make a global grasp of the route optimization problem of express delivery. It provides a reference for the optimization problem of express delivery routes in any other areas.

Keywords: Logistics, Express, Route optimization, GIS

Copyright © 2016 Universitas Ahmad Dahlan. All rights reserved.

1.Introduction

With the rapid development of e-commerce, online shopping has become a popular way. It has contributed to the rapid development of the express delivery industry. The process of logistics distribution mainly divided into two parts. One is picking up the goods from the manufacturer or storage center. Another is transportation and distribution according to the user's address. We define the second one is express delivery. Express delivery is a modern way of circulation, which is the link between suppliers and customers. The most important part is the end distribution directly to the users [1]. Whether the express delivery can be couriered off in time is the main concern for the customers. It involves the issue of distribution route optimization.

Many scholars abroad have studied this kind of problem. The vehicle routing problem was first raised in 1957 [2]. And then many algorithms and methods were studied to solve VRP problem [3-5]. Jose and Jorge studied VRP problem with static target dynamics. Claudia compared VRP problem under unconstrained conditions and VRP problem under the vehicle quantity constraint, which proved the complexity of VRP problem [6]. Francisco used parallel strategy to GPU (Graphics Processing Units) problem [7].

In China, the research of logistics distribution is relatively late, which emerged in the 1990s.The earliest researcher to study the vehicle routing problem is Professor Guo in China. He wrote the first book in the VRP field, which is named vehicle scheduling optimization, with Li Jun [8]. In twenty-first century, with the development of science and technology, the domestic research result of VRP problem has sprung up. Many enterprises developed logistics distribution platform based on GIS (Geographic Information System) technology. Xie Binglei and Li Jun studied VRP problem using genetic algorithm under the condition of the time window and vehicle maximum load [9]. Ji Shouwen put forward a new neural networks algorithm to solve VRP problem [10]. Zhu Qin designed an algorithm of spatial information service optimization based on critical path and response time constraints [11]. Gui Lan studied a traffic network optimization algorithm based on route and simulated annealing [12]. Chen Mo designed and implemented a logistics distribution GIS system [13]. Tu Wei studied the route optimization problem of large scale multi warehouse logistics distribution based on network Voronoi chart [14].

Optimization of express delivery routing is a complicated problem. It involves some issues, such as the establishment of data warehouse, distribution network topology, delivery route algorithm. However, the previous studies have focused on one or two aspects of the problem, which existed bias. This will lead to the whole research system imperfect. Therefore, we need to study the express delivery problem from the whole.

Based on the experience of the previous, this paper presents some key issues of distribution route optimization. There are data warehouse establishment for storing user and map information, establishment of the real distribution network topology, establishment of the algorithm and model of the recommended delivery route and function design based on MapGIS. The purpose of this paper is to global grasp the route optimization problem of express delivery. The results of this paper provide a reference for other areas of the express delivery route optimization problem.

2.Key Technology and Methods

2.1. Spatial Data Warehouse Based on User Information and Address Information

Spatial data warehouse is the application of GIS in data warehouse, which is the future direction of GIS [15]. Through data granularity and effective management, spatial data warehouse can change the application of real-time data in the space database environment. Once the data is deployed, it can satisfy the application of data in different scales and different conditions. Spatial data warehouse is an organization form of storage and management of spatial data, its physical essence is the system of computer storage data.

Nowadays, a large number of users' location data generated in the daily operation in delivery industry. A lot of available information for analysis and mining is hidden in the data. Using the technology of spatial data warehouse to standardize, refine and integrate user information and address information, we can build a spatial data warehouse. The goal is to make basic data processed, cleaned, converted, filed and to establish business logic relationship. It turns a large number of data into the management decision information which plays a key role in the business operation and decision strategy. Constructing the spatial data warehouse by user information and address coding, it will be more effective and profound of spatial analysis and decision application based on spatial information.

2.2. Optimization of Express Delivery Routing Based on GIS Platform

GIS (Geographic Information System) is a computerized database management system. It can collect, store, search, analyse and process the spatial information. With the aid of the computer, it can make the spatial information visualized, which provides a more intuitive and clear expression to users. Especially, it has strong ability of spatial analysis.

Logistics information, which has obvious spatial features, is depends on the geographical space information. Using the integration of GIS technology and logistics management technology, it will fundamentally change the traditional logistics management and analysis model, which can provide quick query-tool, vivid graphics tool and other efficient assistant tool for the masses.

On the one hand, it can collect and quantify the actual road network information by using GIS software platform (such as MapGIS), in order to establish the network topology structure which represents the space relationship among the geographical elements in the distribution area. On the other hand, it also can construct the logistics distribution public information platform based on the GIS and GPS technology, using the location features of GPS, the spatial analysis and visualization of GIS. It can provide reliable platform for space assistant decision-making, which can improve the operation efficiency of the express delivery.

(1) GIS has the powerful ability of spatial data management, which can obtain, store, analyze and process the geospatial information. By using GIS technology, it can manage the related spatial position information and realize the space visualization expression of the customer information, which can provide a basic geographic data source and support for the logistics information service system and logistics decision support system.

(2) Using the network analysis function of the GIS technology, it still can provide the information support and service for the logistics management in e-commerce environment, such as route choice, agency location choice, assistant decision analysis.

(3) By using integration of GIS and GPS technology, we can achieve the real-time tracking of vehicle running data, web sharing and query, replaying of historical running data, etc. 3.Design and Implementation

3.1. Data Warehouse Establishment for Storing User and Map Information

Data warehouse is the key to the modern logistics management decision-making information [16].Spatial data warehouse is actually a mechanism of multi-source data sharing and processing. In this mechanism, users can be access to the database systems of multiple data source through the unified interface of the spatial data warehouse, and ultimately obtain the application of single or integrated digital products.

The purpose of establishing the spatial data warehouse for storage of user and map information is to provide assistant decision support for the e-commerce business administration, business operations and so on.

According to the technical requirements of the spatial data warehouse, the construction of the spatial data warehouse based on users and address information is shown in Figure 1.

(1)Data Source Analysis

The data type of the spatial data warehouse of the user and address information is variety. It mainly includes the following aspects.

- Digital map data: Digital map data mainly refers to the vector map of urban and rural areas, including the data of administrative division, geographic transportation, basic geographic facilities and other data.

- Users' basic information: Users' basic information mainly includes VIP users' name, gender, birthday, mobile phone number, address, e-mail, membership level, order information etc.

- Space address data: The space address data includes users' address data, the address data of distribution center, etc.

- Basic information of express delivery: Basic information of express delivery includes the name, telephone number, distribution area, delivery vehicles, and other information.

- GPS data: GPS data refers to the real-time monitoring and positioning data through handheld GPS devices. It mainly includes the couriers' GPS real-time positioning data, vehicle tracking data, etc.

- Order information: Order information includes the ID number, details information, receipt address of the order, booking time, payment information, etc.

(2)Design of the Spatial Data Warehouse

The key question of the construction of spatial data warehouse is how to determine each application subject, how to design the storage model, and how to extract data efficiently.

1) Subject determination

In the courier business process, there are some subjects of the data mining. Such as planning the service range of couriers, assessing the delivery time of couriers. In the choice of subject, the most important one will be used to be the touchstone for the design of data warehouse. In this research, we choose the assessment the delivery time of the courier as a subject.

2) Design of multidimensional data model

The spatial data warehouse often uses the multidimensional data model to store the data. The dimension model mainly includes the star model, the snowflake model, the fact constellation model, etc. In this research, we use the star model to design the spatial data warehouse model. The star model is composed by the fact table, time dimension, space dimension and theme dimension. In this paper, the star model chart is designed based on the fact table of the users. The star model diagram is as shown below Figure 2.

- Design of the fact table

The fact table is the place where the real data is stored. In the star model, the fact table is expressed by the center of the star. It has two components. One is the primary key of the dimension table including the user coding, time coding, address coding, order coding. They constitute the combination keys of the fact table. Another is the measurement of the data warehouse, the distribution quantity and distribution chart.

- Design of the dimension table

After design of the real table, we can determine what kind of dimension tables will be created. Through the analysis results of the theme, we can design the time dimension table, user dimension table, spatial dimension table, order dimension table, etc. Through the multidimensional combination, we can carry out the fast statistical analysis and trend analysis quickly.

(3)ETL Process of Spatial Data Warehouse

In the process of building data warehouse, the design and operation of ETL is the biggest and the most complex part [17,18].

The special data warehouse of storing users and map information requires database software and GIS platform. For the database software, we can use Oracle, SQL Server and other database management software. For GIS software, we can use MapGIS, ArcGIS, etc.

GIS software is mainly used for the spatial data management. Through the ETL tool provided by the system, it can import the data into the data warehouse flexibly and conveniently which can be derived from SQL, Server DB2, Oracle, Access and other data sources such as Excel and other data sources. The ETL flow of the spatial data warehouse is shown as follows Figure 3.

3.2. Establishment of the Real Distribution Network Topology

At present, most of the map that can be bought is the traffic map, which only contains simple topological relations among the roads of the map. It is not only accurate enough to be used in the distribution route optimization, but also unable to provide the topological relationship between customers and map that is considered in line optimization.

In order to be able to carry on the network analysis, it is necessary to establish the topological relationship of the space network. And the establishment of the correct road network topology is the premise of the implement of the optimal path planning. The method of network topology construction is mainly divided into the following processes:

(1) Extraction and construction of urban road network topology

Firstly, extract the road information from the original road file. Topological check, cut down and generate the set of mutually disjoint section. At the same time, make the definition of the node, the halfway position coordinates and the section attribute feature.

Moreover, check the topology fault and piece using the data structure to establish the topological relationship of the road in order to generate the road network topology.

(2) Topology rendering based on the mobile terminal

At present, the digital map only shows the village level, the detailed address cannot be displayed on the map. With the aid of the real address data collected by the courier delivery, we can complement and improve the existing digital map and obtain more accurate map.

For the customer point that the city road cannot reach or comes from the remote areas, we can use GPS mobile terminal to access to the internal data in real time. The topology of the inner street data is added and drawn by using GIS software at the server side, in order to improve the road network information and achieve the precise navigation.

(3) Matching the customer point and road network

Combined with the daily distribution route data of the express delivery, we study the rules and methods of the matching to match the customer information and the corresponding road and to build the distribution network. Furthermore, abstract the digital map and the customer point information acquired by GPS, establish the distribution network between the distribution center and the customers. Consequently, generate the distribution network topology.

3.3. Establishment of the Algorithm and Model of the Recommended Delivery Route

Establish the optimal distribution model. For the vehicle delivery, achieve the optimization balance between the time and the cost. For the delivery couriers, enhance the performance of the courier and take the users' satisfaction for the optimal.

The recommended delivery route algorithm is the core of the optimal path planning. The path analysis algorithm in the optimization of distribution route is completed on the basis of the distribution network topology.

3.4.Function Design Based on MapGIS Platform

As the hardware environment, we need web server, GIS server, data server, and so on. The network deployment structure diagram is as shown below Figure 4.

Based on the MapGIS platform, through the Mobile, Web, Server terminal, we design and implement the function, in order to optimize the distribution link, improve the distribution efficiency and improve the users' experience. The function structure is as shown Figure 5.

(1)Couriers' Mobile Terminal

1) Map display and operation: Users can load the map data, supporting the map to zoom in, zoom, drag, fast moving, and so on.

2) Visual localization: Through the couriers' mobile terminal, we can locate the courier position on the GIS map in real time. When the courier reaches the target, it can feedback the real-time location information to the customer.

3) POI information query: The couriers can do the POI querying and positioning according to some keywords. POI information query is shown as follows Figure 6(a).

4) Querying and positioning of the express: According to the ID information of the express parcel, the clients can retrieve distribution address of the delivery parcel, and display on the GIS map. The result of querying and positioning is shown as follows Figure 6 (b).

5) Self-service navigation by GPS: It supports the real navigation of digital map. According to tagging the current position of the courier as the starting point, tagging the delivery address as the end point, and it can be conducted in the navigation (the map supports the inside street data).

6) Planning the optimal path: According to the courier of the task information, the location information and delivery location information, based on the distribution of road network, we can use the recommended courier delivery route algorithm and model to analysis the optimal path. The results of the final calculation are visualized on the GIS map.

7) Collection of inside street (track) data:

Start collecting. Collect the real distribution path, and then display the collected locating point on the map.

Automatic real-time positioning. Open the GPS feature of the phone, start automatic positioning, inside street data can be collected.

Photographic capability. After clicking the photo button, it will enter the camera interface of the phone to take photo. At this time, the information of the photo is saved to the local mobile phone's memory card.

Set the interval time of the positioning. Users can set the interval time value of the automatic positioning, and then automatically record the positioning information in a while.

Path rendering. According to the collected points, the function can automatically calculate the traveled rough distance.

Saving the collected data. The collected data will be saved locally, users can choose to delete or upload according to the actual need.

Uploading the collection track. Select the upload button, the collected path can be uploaded to the server.

8) Tracking of the distribution information: The courier can see the distribution information through the mobile phone. It can realize the tracking and checking of the express.

9) Messages reminding: Setting up the electronic fence among the allocation center, warehouse and users' address, after the vehicle or courier arrived in the range, users can be notified by APP or SMS.

(2) Clients' Web/Mobile Terminal

1) Real-time location of the parcel: The customer with the mobile terminal can query the information of the order logistics, and can display the real-time position of the current package on GIS map. Users can see the real-time location of the current package through the website or APP.

2) Estimation of the arrival time: Users can see the expected arrival time of the current express through the website or APP.

3) Forecast of the express distance: Users can see the location of the current express delivery and forecast the distance with destination through the website or APP.

4) Recording of the order track: Based on the web or mobile GIS map, combined with the logistics information of the order, it can clearly show the logistics track of the orders in real time.

(3) Server Terminal

1) Map display and operation: It includes the map browsing, layer controlling, hawkeye, measurement, selection, annotation, map editing, and so on.

2) Querying of the comprehensive information: On the GIS map, we can query and track not only the delivery of goods, but also the map and courier information.

3) Rendering of the inside street data: To add and draw the topology of inner street data with MapGIS software in server side, which is uploaded with GPS mobile terminal by the courier real-time acquisition inner street data, in order to improve the topology of the road network.

4) Real-time monitoring by GPS: Real-time monitoring by GPS, that is, displaying the real-time position and other information of the monitored objects (such as the distribution vehicles) on the map, which can instantly understand the basic situation of the monitored object.

5) Playbacking the GPS historical track of the vehicle: Through setting the start time and end time of the delivery vehicles, it can playback the historical track of the vehicle at a certain time on the digital map, in order to reach the information tracking management of the vehicles. Figure 7 reflects the vehicle GPS historical track playback.

6) Distribution route planning: By using GPS and GIS technology, according to the customer's geographic location information and logistics center location information, we can calculate the shortest path between the client and the logistics center, between the couriers and customers based on the road network. With the couriers' mobile side, it can form the optimal distribution route to improve the delivery efficiency.

7) Data analysis (track, order data, etc.): Through the technology of big data analysis, mining the potential information of the location data to grasp the users' characteristics and optimize the distribution experience. For example, deeply analysing the number of visitors, sales, orders and conversion rate of the customers contributes to select the advertising channels to achieve the accurate delivery.

4.Conclusion

In the link of express delivery, efficiency is the point. On the one hand, we need to provide the satisfaction of the delivery service, and maintain high efficiency of the distribution to improve the customers' satisfaction. On the other hand, we need to design a reasonable distribution path and use fewer vehicles to improve the loading rate of distribution vehicles and reduce the transportation costs. For that, this paper described the key issues of the route optimization of express delivery. It includes the establishment of data warehouse for storing user and map information, establishment of the real distribution network topology, establishment of the algorithm and model of the recommended delivery route, the function design based on the MapGIS platform.

In future work, the path optimization model and algorithm are needed to research deeply. In addition, how to use the method and technology of big data to design the reasonable delivery route is another aspect. A reasonable delivery route can reduce the working time and labor intensity of the courier. So, the research has an important signification to improve the efficiency of the work and the customers' shopping satisfaction.

Acknowledgements

This work was supported by the Central Universities under Grant CUGL130259.

References

References

[1] H Yan, C Peng, H Li. Implementation of optimum route of logistics distribution based on android. Computer& Digital Engineering. 2014; 42(9): 1624-1627.

[2] GB Dantzig, JH Ramser. The Truck Dispatching Problem. Management Science. 1959; 6(1): 80-91.

[3] S Eilon, CDT Watson-Gandy, N Christofides. Distribution Management-Mathematical Modelling and Practical Analysis. IEEE Transactions on Systems Man & Cybernetics. 1974; SMC-4(6): 589-589.

[4] M Gendreau, G Laporte. A tabu search heuristic for the vehicle routing problem. Management Science. 1991; 40(10): 1276-1290.

[5] Yu Kanhua. Urban Planning Support System Based on Three Dimensional GIS. TELKOMNIKA Indonesian Journal of Electrical Engineering. 2014; 12(5): 3928-3935.

[6] C Archetti, D Feillet, M Gendreau. Complexity of the VRP and SDVRP. Transportation Research. 2011; 19(5): 741-750.

[7] S Tsutsui, N Fujimoto. ACO with tabu search on a GPU for solving QAPs using move-cost adjusted thread assignment. Genetic and Evolutionary Computation Conference. 2011; 1547-1554.

[8] BL Xie, J Li, YH Guo. Genetic algorithm for vehicle scheduling problem of non-full loads with time windows. Journal of Systems Engineering. 2000; 3(15): 290-294.

[9] SW Ji, LX Miao, KQ Li. Optimal Truck Scheduling Method. Journal of Highway and Transportation Research and Development. 2003; 6(20): 109-112.

[10] Q Zhu. Optimal Composition Algorithm for Spatial Information Service Based on Critical Path and Response Time Constraint. Geomatics and Information Science of Wuhan University. 2007; 32(11): 1042-1045.

[11] G Lan, JY Gong. Path-based and SA-based Algorithm for Transportation Network Design Problem. Geomatics and Information Science of Wuhan University. 2008; 33(4):388-392.

[12] W Tu, QQ Li, ZX Fang. Large Scale Multi-depot Logistics Routing Optimization Based on Network. Acta Geodaetica et Cartographica Sinica. 2014; 43(10): 1075-1082.

[13] Abdelrahman AS, Abd-Allah MAA. New Techniques for Disconnector Switching VFT Mitigation in GIS. International Journal of Electrical and Computer Engineering (IJECE). 2014; 4(2): 179-192.

[14] SY Kang, M Kang. Database-A Key to Information Decision Making of Modern Department Store's Logistics Management. Commercial Research. 2002; (09): 23-27.

[15] Abdar M, Kalhori SRN, Sutikno T, Subroto IMI, Arji G. Comparing Performance of Data Mining Algorithms in Prediction Heart Diseases. International Journal of Electrical and Computer Engineering (IJECE). 2015; 5(6): 1569-1576.

[16]

[17] KH Strange. ETL Was the Key to This Data Warehouse's Success. Technical Report CS-15-3143. 2002.

[18] A Simitsis, P Vassiliadis, TK Sellis. Extraction-Transformation-Loading Processes. Encyclopedia of Database Technologies & Applications. 2005.

[19] Kanhua Y. Urban Planning Support System Based on Three Dimensional GIS. TELKOMNIKA Indonesian Journal of Electrical Engineering. 2014; 12(5): 3928-3935.