CN-121981637-A - Semi-open vehicle path optimization method and system considering repartition

CN121981637ACN 121981637 ACN121981637 ACN 121981637ACN-121981637-A

Abstract

The invention discloses a semi-open vehicle path optimization method and system considering repartition. Relates to the field of traffic optimization. The method comprises the steps of obtaining position information, recycling demand information, goods delivery demand information, vehicle parameter information and time data of nodes in a distribution network of a full-channel retail distribution network, adopting Euclidean distance as distance among the nodes and calculating running time among the nodes according to the vehicle parameter information, constructing a path optimization model, decomposing the path optimization model based on arcs into main problems and sub problems through Dantzig-Wolfe decomposition, constructing a branch pricing cutting algorithm based on the decomposed main problems and sub problems, and solving the main problems and the sub problems to obtain an optimal distribution scheme. The invention can obtain the optimal distribution scheme, has good effect in the large-scale optimization problem, and can provide a corresponding distribution scheme for all-channel retail enterprises.

Inventors

XU SHUXIAN
HE YING
SONG YUANYUAN
LI YUE
TAN XIAOYU
Ling shuai
YANG DAOYUAN
CHANG XING

Assignees

天津大学
交通运输部规划研究院

Dates

Publication Date: 20260505
Application Date: 20260211

Claims (7)

1. A method of optimizing a semi-open vehicle path in consideration of reassignment, comprising: Step 1, acquiring position information of warehouses, retail stores and clients in a full-channel retail distribution network, store replenishment and recovery demand information, client order taking and delivery demand information, vehicle parameter information and time data of each node in the distribution network; step 2, using Euclidean distance as the distance between each node, and calculating the running time between each node according to the vehicle parameter information; step 3, constructing an arc-based path optimization model, and decomposing the arc-based path optimization model into a main problem and a sub problem through Dantzig-Wolfe decomposition; Step4, constructing a branch pricing cutting algorithm based on the decomposed main questions and sub questions; And 5, solving the main problem and the sub problem based on the information data in the step 1, the running time in the step 2 and the algorithm in the step 4 to obtain an optimal distribution scheme.
2. A method of optimizing a semi-open vehicle path in consideration of re-dispatch as claimed in claim 1, wherein the path optimization model is based on a total cost minimum as an objective function and considers constraints of vehicle hard time window constraints, vehicle capacity constraints and vehicle maximum distance of travel constraints.
3. The method for optimizing the semi-open vehicle path taking re-dispatch into consideration according to claim 1, wherein the branch pricing cutting algorithm constructed in the step 4 is designed to solve a sub-problem by a bidirectional label algorithm adapted to the problem characteristics, and an acceleration strategy is embedded to improve the solving efficiency, 3 branch strategies are adopted in a branch-and-bound frame, and a greedy plug-in algorithm is designed to solve an initial vehicle path scheme at a branch-and-bound root node.
4. A method of optimizing a vehicle path in consideration of re-dispatch according to claim 3, wherein said bi-directional label algorithm comprises a forward label algorithm, a backward label algorithm and a connection rule.
5. A method of optimizing a semi-open vehicle path with re-dispatch in view of claim 3, wherein said branching strategy comprises a vehicle number based branching strategy, an arc flow based branching strategy, and a two node set output arc flow based branching strategy.
6. A method for optimizing a semi-open vehicle path with re-dispatch in mind according to claim 3, wherein in step 4, an initial vehicle path plan is generated using a greedy plug-in algorithm, comprising the steps of: initializing, namely putting all clients to be accessed and store vertices into a set, creating empty paths corresponding to different warehouse combinations, and storing the empty paths into an initial path set; Iterative interpolation when there are non-accessed clients or store vertices, the loop performs the following operations: traversing all non-accessed clients and store vertices, all paths and insertion positions in the paths to form a feasible insertion scheme set; for each feasible insertion scheme, calculating the cost increment after insertion, and selecting the insertion scheme with the minimum cost increment; When the original path corresponding to the selected optimal insertion scheme is an empty path, copying the empty path, executing insertion operation, and adding the obtained path into an initial path set to ensure that the empty path of each warehouse combination is always reserved; Removing the vertex from the unvisited set of customer store vertices; outputting the result, namely returning all non-empty paths in the initial path set as initial feasible solutions after all vertexes are inserted.
7. A re-dispatch-considered semi-open vehicle path optimization system, comprising: The data acquisition module is used for acquiring the position information of warehouses, retail stores and clients in the full-channel retail distribution network, store replenishment and recovery demand information, client order delivery demand information, vehicle parameter information and time data of each node in the distribution network; The distance and time calculation module adopts Euclidean distance as the distance between the nodes and calculates the running time between the nodes according to the vehicle parameter information; The model construction module is used for constructing a path optimization model based on arcs and decomposing the path optimization model based on the arcs into main problems and sub-problems through Dantzig-Wolfe decomposition; the algorithm design module is used for constructing a branch pricing cutting algorithm based on the decomposed main problems and the decomposed sub problems; and the iterative optimization module is used for solving the main problem and the sub-problem to obtain an optimal distribution scheme.

Description

Semi-open vehicle path optimization method and system considering repartition Technical Field The invention relates to the field of traffic optimization, in particular to a semi-open vehicle path optimization method and system considering redistribution. Background With the rapid development of electronic commerce, traditional retailers are accelerating the transition to full channel retail models with online-offline convergence. Full channel retail aims to provide a seamless shopping experience for consumers, but also presents a significant challenge to logistics and performance. Retailers need to meet both the inventory restocking needs of off-line stores and the order distribution needs of on-line customers. Meanwhile, the high return rate becomes a prominent problem-data show that the online order return rate in 2019 is usually 15% -40%, which is far higher than 5% -10% of online shopping. In addition, many stores are also subject to management pressures for inventory diapause. Therefore, retailers must handle two logistics tasks simultaneously, namely, recycling the orders from stores, collecting returns from online customers, and restocking physical stores and distributing orders for online customers. These logistics operations are critical to meeting customer expectations and improving overall channel operation efficiency. However, existing research on full channel retail has focused on inventory optimization or order performance, often neglecting the synchronous integration of inventory restocking, order fulfillment and reverse logistics. Furthermore, the distribution activities in the process result in high transportation costs, for example, the logistical cost of amazon in 2018 is 11.89% of the net sales, highlighting the urgency of efficient fleet management and path planning. Thus, designing a distribution system that accommodates the full channel retail needs has become an urgent task for retailers, but current research remains inadequate for this purpose. In reality, some all-channel retailers (e.g., jindong, heaven) often manage the distribution tasks of stores and customers separately. The logistics network is generally composed of a central warehouse, a transfer hub and a store, wherein store replenishment is directly sent from a warehouse by a large vehicle, customer orders are sent to the transfer hub from the central warehouse, and then end distribution is finished by using a small vehicle. Much research has also focused solely on "warehouse-to-store" distribution, or modeling such systems as a multi-stage vehicle path problem. The operation mode of the cutting easily causes the problems of low vehicle utilization rate, large scale of a motorcade, increased running cost and the like. Therefore, the on-line and off-line channel distribution tasks are coordinated and integrated, and the method has important significance for full-channel retail. Therefore, the research provides a novel pick-and-place frame integrating store replenishment, diapause commodity recovery and customer order fulfillment, aims to realize the integrated operation of all-channel logistics through path optimization and resource sharing, reduces the total cost of the system, improves the distribution efficiency and the resource utilization level, and provides a solution for the innovation development of urban logistics and retail supply chains. However, the current path planning method for all-channel logistics has obvious defects that firstly, the existing model presents a cutting state and system integration is lacked. Most of the current researches treat links such as store replenishment, online order fulfillment, return recovery and the like as independent logistic problems to be optimized respectively. Secondly, the existing scheme constraint conditions are stiff, and scheduling flexibility is limited. Most existing models assume that online orders must be shipped by stores, or store restocking can only come from a central warehouse, and this rigid constraint limits the possibility of goods allocation among warehouses, stores and customers, and cannot fully utilize inventory resources of each node in the network, so that globally optimal resource allocation is difficult to achieve. Furthermore, there is a lack of support for accurate and efficient optimization algorithms. The existing research on the vehicle path problem of all-channel logistics is based on a multi-dependency heuristic algorithm. In order to overcome the defects, the invention aims at the minimum total cost including the fixed cost and the transportation cost of the vehicle, builds a semi-open multi-warehouse multi-product unpaired delivery vehicle path optimization model considering the re-distribution, determines the quantity of goods sent by each warehouse and the travelling paths of a fleet service store and a customer, thereby reducing the logistics cost. Disclosure of Invention In view of the above, the present invention provides a method an