CN106600036A - Multi-point express delivery distribution method based on Android - Google Patents

Abstract

Based on the Android multi-point express delivery method, firstly, the starting point, each delivery address and the final destination are stored in the database, and after the delivery member logs in the user interface and obtains the express delivery information form, one-click group SMS notification to the recipient; secondly, combined with Baidu The SDK of the map application finds the optimal path through the global path optimization and local path optimization in the A* algorithm; then displays the planned path in the form of text or a map, and can also add a voice broadcast function to broadcast the current optimal path. Delivery route; finally, write computer software to meet the operation of any Android mobile terminal. The present invention can intelligently realize the planning of delivery routes and improve delivery efficiency.

Description

Android-based multi-point express delivery method

technical field

The present invention relates to an express delivery method. Based on the optimal path planning of Android multi-point express delivery, the A* algorithm is used for path planning according to the specific delivery environment and delivery task requirements. , and conform to the optimal path of environmental information to ensure that the delivery staff can efficiently complete the specified delivery tasks, thereby improving work efficiency.

Background technique

With the rapid development of e-commerce and popular online shopping, express delivery has become a modern circulation method and a link between suppliers and customers. However, at present, China's express delivery industry is still in a stage of development that relies heavily on labor. Especially in the delivery link, the delivery efficiency of each courier varies greatly, and the time wasted and economic costs are immeasurable. The most important problem is the delivery route. optimization problem. In recent years, with the rise of the Internet of Things, information technology has also been gradually applied to the express delivery industry, and further gave birth to the emerging concept of "smart logistics". The optimal path of express delivery has a great impact on speeding up delivery, improving service quality, reducing delivery costs and increasing economic benefits, and the optimal delivery path planning based on Android multi-point express delivery is to simulate the "last mile" of express delivery The process enables it to generate distribution routes according to the strategy of the shortest distance and the least time, improve work efficiency, and alleviate the current situation that the logistics industry is in short supply. Therefore, how to let the delivery staff use Android mobile phones to efficiently complete the delivery task, so as to improve the inventory management ability and loading capacity of e-commerce is one of the hot spots in the current logistics and distribution field.

At present, the research on express distribution mainly focuses on the problem of transportation cost, and the path planning algorithm is one of the core technologies in the field of logistics distribution. There are few researches on the realization of path planning for specific distribution environments and specific dispatch tasks. Compared with the traditional express delivery work, Lei Peng mainly researched the software design level in the design and implementation of the express delivery software based on the Android system, but did not study the delivery route method, and could not provide help in solving the planning of the express delivery route ( Design and implementation of express delivery software based on Android system [D]. University of Electronic Science and Technology of China, 2014.); He Ping proposed an intelligent express delivery method on the mobile platform. Inefficiency, the common goal of the heavy burden of the delivery staff, but did not give a specific application platform and map application SDK, the selected algorithm is the greedy algorithm with roulette and the global k-opt method to plan the optimal delivery route, they It can solve some basic tasks in path planning, but they all need to be planned in order and segmented according to the order of task nodes. The planned path is affected by the number and order of task nodes, and the optimality of the planned path cannot be guaranteed. Good for complex tasks in distribution systems (Smart express delivery methods on mobile platforms: China, 201510522278.X[P].2015-08-24.).

Contents of the invention

The present invention overcomes the above-mentioned shortcoming of prior art, develops and designs the multi-point express delivery method based on the Android platform. The present invention adopts A* algorithm to carry out the path planning method to find the optimal path, and its specific process is shown in Figure 1, which can be mainly divided into two parts: establishing bmob database and combining Baidu map path optimization. Firstly, the starting point, each delivery address and final destination are stored in the database, and after the courier logs in the user interface and obtains the courier delivery information form, one-click group SMS notification is sent to the recipients; secondly, combined with the SDK of Baidu map application, through A* The global path optimization and local path optimization in the algorithm find the optimal path; then the planned path is displayed in the form of text or a map, and a voice broadcast function can also be added to broadcast the current optimal delivery route; finally, the computer program The software satisfies the operation of any Android mobile terminal. Its technical solution is:

The Android-based multi-point express delivery method includes the following steps:

Step 1: Create a database on the bmob mobile terminal, store the starting point, each delivery address and final destination in the database, and at the same time, the delivery staff enters the user login interface, and after logging in to the account, obtains the express delivery task list, and sends one-click group SMS to the recipients . The database contains the courier details table and the delivery location information table, and it is allowed to delete part of the entered addresses due to incorrect input during the input process.

Step 2: Combined with the SDK of Baidu Maps application, use the A* global route optimization algorithm to plan the optimal delivery route before departure. The A* algorithm is currently the most popular heuristic search algorithm. For each new state (or new node) encountered in the search process, first calculate its best cost estimate according to the evaluation function, and then select the estimated value at that time The smallest state, from which the search continues, and the best-first search is based on the estimated value of the node's cost. Next, the optimal route planning method is described: First, call the SDK of the Baidu map application open to developers, obtain the corresponding latitude and longitude according to the input text address, and then calculate each pair of addresses based on the latitude and longitude and surrounding road information The shortest traffic distance between couriers, use the A* global path optimization algorithm to search for the global optimal path that meets the task requirements, and find the optimal delivery path before departure. For each new state encountered in the search process, the A* algorithm first calculates its best cost estimation value according to the evaluation function, and then selects the state with the smallest estimated value at that time, and continues to search from this state until a possible value is found. Sexual end point.

Step 3: For problems such as undeliverable delivery, change of delivery address or new pick-up order during the delivery process, use the A* algorithm to re-plan the current optimal delivery route. When the courier learns of some temporary changes during the delivery process, such as failure to deliver, change of delivery address, or receiving a new pickup order, etc., he must first call the SDK of the Baidu Maps application to obtain the latitude and longitude of the current address, and update the current address Add it to the address database, delete addresses that do not need to be delivered, and add updated delivery addresses and addresses that require pickup; next, define a current set of planable addresses, including all addresses that have not yet been delivered, and calculate each new Increase the point-to-point distance between the address and other addresses in the set, use the A* global path optimization algorithm to plan an initial delivery route for the remaining addresses, and then use the current location as the starting point, and plan the address set as the planning target, starting from the current Starting from the location, use the A* global path optimization algorithm in the set of planable addresses, select the next delivery address according to the calculated point-to-point distance in the set, remove this address from the set of planable addresses, and put It is used as the current address of the next round, and the above steps are repeated until the set of planable addresses is empty, and finally connected to the destination to form an initial current express delivery route; finally, the local path planning of the A* algorithm is used to plan the initial The route is further optimized, and local operations are performed within the scope of the planable address set, the current location and the destination, and it is necessary to ensure that the newly formed route is a partial route starting from the current location, passing through the planable address set, and finally reaching the destination , and then repeat the operation until it cannot be improved, and finally get the current optimal delivery route.

Step 4: Display the details of the planned optimal route in the form of text and a map. If necessary, you can use the voice broadcast function to broadcast the current optimal delivery express route in real time.

Finally, the above steps are all carried out through the written computer software, which is suitable for any Android mobile terminal, which is simple to operate but meets the delivery requirements, and transmits the results obtained in step 4 to the Android mobile terminal carried by the delivery staff. It consists of four parts, the first part is to establish the mobile terminal database, the second part is to initially plan the optimal delivery route, the third part is to re-plan the current optimal route, and the fourth part is the distribution of the delivery staff. The delivery staff does not need to enter the tedious operation of the task formula, but only needs to store the starting point, each delivery address and the final destination in the database, and click to plan the route. The operation is simple and easy. After obtaining the optimal planned route, the delivery staff only need to bring the Android mobile terminal and choose any means of transportation to carry out express delivery.

From the perspective of the courier, the present invention develops an application program suitable for the courier to efficiently deliver the courier. The courier can input the address to be delivered in the application program, and then the application program intelligently plans an optimal route According to the map, the courier can efficiently complete the delivery task according to the searched route map, and deliver the courier to the customer in the fastest time to satisfy the customer. It can increase the number of customers and reduce the manpower, material and financial resources of delivery, etc. cost.

The present invention is a multi-point express delivery system built on the Android mobile platform, including the starting point, multiple delivery addresses and the final destination, combined with the SDK of Baidu map application, using the A* algorithm to plan the optimal delivery route before departure, and according to Changes in road conditions are modified in real time, and the details of the optimal route are displayed in the form of text and maps. The invention solves the defects of low efficiency of express delivery, waste of manpower and delay of express delivery. The present invention adopts the global A* method, which can optimize the express delivery route before delivery; and adopts the local A* method to construct a planable address set, and then optimizes the follow-up route on the basis of not affecting the route already passed, which not only makes the express delivery company The distribution efficiency is basically guaranteed, and it can also free the courier from the burden of distribution route planning, reflecting the key to the quality of distribution services and realizing real smart logistics.

The present invention has following advantage:

(1) This optimal path planning method for multi-point express delivery based on the Android mobile platform can choose different means of transportation during delivery, and has very low requirements for vehicle configuration. It does not need to be equipped with GPS, and tricycles can be used. The choice of transportation mode is flexible, so it can be widely promoted.

(2) The development platform of this invention is relatively popular, and only needs to carry Android mobile devices, which is convenient for couriers to carry and use; in addition, combined with Baidu map application, using map visualization and voice navigation functions, the delivery route is clear at a glance, providing users with all Specific delivery information, rich in functions, makes the delivery work quality get rid of human factors as much as possible, and achieve a standardized effect, even new couriers who don't know the way can complete the delivery task very well.

(3) In response to some temporary changes in the delivery of the courier, such as failure to deliver, change of delivery address, or receipt of a new pick-up order, etc., the previous dynamic planning was generally arranged in the central delivery system on the server side. Then send the command to each vehicle. However, the characteristic of express delivery is that the courier directly obtains the first-hand information, and the courier arranges it by himself. However, our optimal route planning method for multi-point express delivery based on the Android mobile platform can be directly flexible by the courier in this respect. Response is high in real time.

(4) This optimal path planning method for multi-point express delivery on the Android mobile platform is based on the global path planning and local path planning of the A* algorithm, which can produce better initial solutions than random or greedy algorithms; using A* global The path planning method can optimize the express delivery route before delivery; and the A* partial path planning method can continue to optimize the follow-up path on the basis of not affecting the already passed route by constructing a planable address set, so that the entire delivery path reaches best.

Description of drawings

Fig. 1 is the schematic flow chart of the present invention

Fig. 2 is the user login interface of the present invention

Fig. 3 is the short message one-key group sending interface of the present invention

Fig. 4 is Baidu map import figure of the present invention

Fig. 5 is a map of the acquisition and delivery interface of the present invention, wherein A is the Pingfeng Campus of Zhejiang University of Technology, B is Zhejiang University (Zijingang Campus), C is Zhejiang University (Yuquan Campus), D is Zhaohui Campus of Zhejiang University of Technology, and E is Hangzhou North Bus Station.

Fig. 6 is the path planning implementation result of the present invention.

detailed description

The following is a simple example of the Android-based multi-point express distribution optimal route planning method of the present invention in conjunction with the accompanying drawings. Select A, B, C, D, and E as the address of the recipient in Hangzhou for express delivery: point A is the starting point, and after the express delivery is completed, you will eventually return to point A, and you need to pass through B, C, D, and E on the way. A courier delivery point. First, store the address information of these points in the bmob database. After the delivery staff logs in to the account on the Android mobile terminal, they will obtain their information and send text messages to inform the recipients in advance that the courier will arrive; Get the optimal route key on the mobile terminal to realize the route planning before departure, and display the first best point C; after the courier arrives at point C, click the obtain optimal route key to re-plan the current location until the completion Express delivery at all points, and return to point A, the specific route planning is shown in Figure 6.

The present invention is based on the Android multi-point express distribution optimal path planning method mainly has the following contents: First, it is necessary to establish a database on the bmob mobile terminal, store the starting point, each delivery address and the final destination into the database, and at the same time, the delivery staff enters the user login interface and logs in Obtain the express delivery task list after account number; then combine the SDK of Baidu Maps application, use the A* global path optimization algorithm to plan the optimal delivery route before departure; for the failure of delivery during the delivery process, change the delivery address or add new pickups For issues such as orders, use the A* algorithm to re-plan the current optimal delivery route; finally, display the details of the optimal route and navigate the optimal delivery route (see Figure 1 for the specific process).

The present invention mainly uses Android SDK, Baidu map API, and navigation SDK. The task of express delivery is mainly to reduce delivery costs and meet customer needs. Therefore, one of the main directions that express companies consider is how to reduce costs as much as possible while ensuring customer satisfaction. The key to reducing costs is to find an optimal path. . However, the present invention applies advanced information technology to express delivery route planning, which not only enables the express delivery company to obtain the basic guarantee of delivery efficiency, but also frees the courier from the burden of delivery route planning, realizing real smart logistics. Here, the A* global path optimization algorithm is mainly used to plan the optimal path before departure, and for problems such as undeliverable delivery, change of delivery address, or new pick-up order during the delivery process, the A* global path optimization algorithm and local The combination of route optimization algorithms re-plans the current optimal delivery route, so that the delivery route is optimal throughout the delivery process and the delivery burden of the courier is reduced.

The present invention is based on the optimal path planning method for Android multi-point express delivery, and its features mainly follow the steps, as shown in Figure 1:

Step 1. Establish a database on the bmob mobile terminal, and store the starting point, each delivery address and final destination into the database. The database includes a express delivery details table and a delivery location information table. At the same time, the courier enters the user login interface, as shown in Figure 2. After logging in to the account, he obtains the express delivery task list, and sends one-click group SMS to the recipients to facilitate them to receive the express, as shown in Figure 3. Express delivery details include order number, sender's name, sender's phone number, place of origin, sender's detailed address, sender's unit name, recipient's name, recipient's phone number, destination, recipient's details Address, recipient unit name, total cost, payment method, weight, number of pieces, and date of delivery. As the deliveryman who enters the software for the first time to add an address, there is no information prompt in the database, but the deliveryman enters the address into the database. If the same or similar address is entered again, the memory function of the database will prompt to provide convenience for the user. During the input process, it is allowed to delete part of the entered address due to incorrect input;

Step 2, combined with the SDK of the Baidu map application, use the A* global route optimization algorithm to plan the optimal delivery route before departure. Firstly, Baidu Map is invoked, and the corresponding longitude and latitude are obtained according to the input text address, and then positioning is performed based on the longitude and latitude and surrounding road information, as shown in Figure 4. Then, according to the input address information, it is displayed on the map, as shown in Figure 5, and the shortest traffic distance suitable for couriers between each pair of addresses is calculated, and the A* global path optimization algorithm is used to search for a global location that meets the task requirements. Optimal route, find the optimal delivery route before departure;

Step 3. For problems such as inability to deliver, change of delivery address, or new pick-up order during the delivery process, as shown in Figure 5, it is necessary to re-call the SDK of the Baidu Map application to obtain the latitude and longitude of the current address and add it to the address In the database, remove the addresses that no longer need to be delivered, and add updated delivery addresses and addresses that require pickup. Use the A* algorithm again to replan the current optimal delivery route. Next, define a current planable address set, including all addresses that have not yet been delivered, calculate the point-to-point distance between each newly added address and other addresses in the set, and use the A* global path optimization algorithm to plan an address for the remaining addresses For the initial delivery route, the current location is taken as the starting point, and the planable address set is used as the planning target. Starting from the current location, the A* global path optimization algorithm is used in the planable address set, and the point pairs in the calculated set are used. distance, select the next delivery address, remove this address from the set of addressable addresses, and use it as the current address for the next round, repeat the above steps until the set of addressable addresses is empty, and finally connect to the destination, Form an initial current express delivery route; finally, use the local route planning of the A* algorithm to further optimize the initial route, perform local operations within the scope of the planable address set, current location and destination, and ensure that the new The formed route is a partial route starting from the current location, passing through a set of planable addresses, and finally reaching the destination, and then repeated operations until it cannot be improved, and finally obtains the current optimal delivery route, as shown in Figure 6;

Step 4: Display the details of the planned optimal route in the form of text and a map. If necessary, you can use the voice broadcast function to broadcast the current optimal delivery express route in real time;

Step 5. Through the computer software system, the operation of any Android mobile terminal is satisfied, and the result obtained in step 4 is transmitted to the Android mobile terminal carried by the courier. You can see the order of delivery and specific route information, such as distance, time, etc. You can also use detailed text to explain the specific route. Due to the limitation of the mobile phone screen and the existence of many planned addresses, it is not easy to view the route on the Baidu map. You can use this function to display the detailed list of the route to understand the order of the locations. If necessary, the voice broadcast function can be selected to broadcast the current optimal delivery express route in real time, and the express delivery can be delivered to the customer quickly and completely.

Claims (3)

1. Android multiple spot express delivery allocators are based on, are comprised the following steps：

Starting point, each dispensing address and final destination are deposited into data base by step 1, the data base for setting up bmob mobile terminals, Simultaneously dispensing person enters User logs in interface, express delivery is obtained after login account and distributes task list, and it is short to carry out a key to addressee Letter mass-sending, comprising express delivery details table and delivery location information table in data base, allows because of mistake input in input process Delete the partial address of typing；

Step 2, with reference to the SDK of Baidu map application, the optimum dispensing road before being set out using the planning of A* global paths optimizing algorithm Footpath, the description of optimal route planing method：First, the SDK for calling Baidu map application to open to developer, according to the word of input Address, obtains its corresponding longitude and latitude；The road information of longitude and latitude and periphery is then based on, is calculated between each pair address and is fitted The logical distance of most short delivery of courier is closed, using the search of A* global paths optimizing algorithm the global optimum of mission requirements is met Path, finds the optimum Distribution path before setting out；A* algorithms for each new state run in search procedure, first by appraisal letter Number calculates its optimal cost assessment values, then selects the minimum state of assessment values at that time, starts to continue search for from the state, Until searching out the larger terminal of probability；

Step 3, for what is occurred in delivery process cannot dispense, dispenses address modification or newly-increased pickup order problem, again Current optimum Distribution path is planned again using A* algorithms：When courier learns some Iterim Change situations in delivery process, Cannot such as dispense, dispense address change, or when being connected to new pickup order problem, need to first call the SDK of Baidu map application The longitude and latitude of current address is obtained, and current address is added in address database, delete the address without the need for dispensing again, while Increase dispense address and the requirement for updating and go to the address of pickup；Next, a current address set planned is defined, comprising All addresses for not yet dispensing, calculate each and Add Address and adjust the distance with the point in set between other addresses, global using A* Optimum path search algorithm is that address space left plans an initial distribution route, then using current location as starting point, can plan ground As the object of planning in the set of location, from the beginning of current location, A* global path optimizing algorithms are utilized in it can plan address set, Adjust the distance according to the point in the set that calculates, select next dispensing address, by the address from can plan in address set Remove, and it is repeated above step as the current address of next round, until address set can be planned for sky, finally and mesh Ground be connected, formed an initial current express delivery distribution route；Finally, recycle the local paths planning of A* algorithms first to this Beginning route is further optimized, and carry out partial operation in the range of address set and current location and destination planning, And to guarantee new composition route be one from current location, process can plan address set, be finally reached destination Local route, then by the way that operation is repeated several times until cannot improve, finally gives current optimum distribution route；

Step 4, the optimal route details planned is shown in the form of word and map, it may be necessary to select voice Report function, the current optimum dispensing express delivery route of real-time broadcasting；

Step 5, by computer software, meets the operation of any Android mobile terminals, and the result that step 4 is obtained is passed On the defeated Android mobile terminals carried to dispensing person.

2. it is according to claim 1 based on Android multiple spot express delivery allocators, it is characterised in that to tie in the step 2 The SDK of Baidu map application is closed, the optimum Distribution path before being set out using the global path optimizing planning of A* algorithms, and to dispensing During the express delivery information that occurs the problems such as change, reuse A* global paths optimizing algorithm and plan current optimum dispensing again Path.

3. it is according to claim 2 based on Android multiple spot express delivery allocators, it is characterised in that right in the step 3 Some Iterim Change situations are learnt in delivery process in courier, cannot such as be dispensed, be dispensed address change, or be connected to new The problems such as express delivery information such as pickup order is changed, reuse formed after A* global path optimizing algorithms are planned again one it is new After current express delivery distribution route, the local paths planning for recycling A* algorithms is further optimized to the original route, Can plan carry out partial operation in the range of address set and current location and destination, and guarantee that the new route for constituting is one From current location, process can plan address set, be finally reached the local route of destination, then by the way that behaviour is repeated several times Make, up to improving, to finally give current optimum distribution route.