CN-122022252-A - Method for dispatching freight vehicles, storage medium and computer program product

CN122022252ACN 122022252 ACN122022252 ACN 122022252ACN-122022252-A

Abstract

The application discloses a freight vehicle dispatching method, a storage medium and a computer program product, which relate to the technical field of dispatching optimization and comprise the steps of realizing trailer exchange of vehicles with different transportation tasks on the way by introducing a change hanging node, thereby reducing the idle driving distance and improving the resource utilization rate, simultaneously, establishing a freight vehicle dispatching model with time constraint for ensuring that high-efficiency goods can be delivered on time, and combining mathematical planning and an accurate algorithm to realize optimal solution. The application solves the technical problem of poor dispatching effect in the conventional freight dispatching scheme.

Inventors

XUE ZHAOJIE
JIANG JIAYI
PENG WENXIANG

Assignees

深圳大学

Dates

Publication Date: 20260512
Application Date: 20251224

Claims (10)

1. A method of scheduling a freight vehicle, the method comprising: constructing a candidate change-hanging combination set based on received freight vehicle dispatching data, wherein the freight vehicle dispatching data at least comprises change-hanging nodes for changing and hanging all freight vehicles; Calculating a dual variable of the limited main problem corresponding to the candidate change-hanging combination set, and searching a target change-hanging combination in each change-hanging node based on the dual variable; under the condition that a target change combination is found in each change-hanging node, adding the target change-hanging combination into the candidate change-hanging combination set to obtain a new candidate change-hanging combination set, wherein the total cost of the new candidate change-hanging combination set is smaller than that of the candidate change-hanging combination set; And executing the step of calculating the dual variable of the limited main problem based on the new candidate change-hanging combination set, and converting the candidate change-hanging combination set into an optimal solution output meeting integer constraint under the condition that the target change-hanging combination is not found in each change-hanging node.
2. The method of claim 1, wherein the step of constructing a candidate set of change-over combinations based on received freight vehicle dispatch data comprises: Receiving freight vehicle dispatching data, wherein the freight vehicle dispatching data also comprises transport tasks corresponding to all freight vehicles; determining an independent transport combination for each of the freight vehicles to independently complete an associated transport task based on the freight vehicle scheduling data; Determining a feasible hanger changing combination of the hanger changing between every two freight vehicles based on the freight vehicle dispatching data, wherein the feasible hanger changing combination meets the time sequence constraint between the freight vehicles; integrating the independent transportation combination and the feasible hanging combination into a candidate hanging combination set, wherein each freight vehicle in the candidate hanging combination set is at least covered by one candidate hanging combination, and the candidate hanging combination comprises the independent transportation combination and the feasible hanging combination.
3. The method of claim 2, wherein the step of calculating the dual variables of the candidate set of change-over combinations corresponding to the restricted master question comprises: constructing a limited main question based on the candidate change-hanging combination set; And solving the limited main problem based on a preset linear programming solver, and extracting the dual variables of each freight vehicle from the output of the preset linear programming solver when the optimal solution of the total cost is obtained, wherein the dual variables correspond to constraint conditions in the limited main problem, and the constraint conditions are that each freight vehicle can only be hung once.
4. The method of claim 1, wherein the step of locating a target swap combination in each swap node based on the dual variables comprises: Constructing each searching sub-graph corresponding to each hanging node based on the dual vector, wherein each graph node in the searching sub-graph represents each freight vehicle, and each directed arc in the searching sub-graph represents the hanging sequence among the freight vehicles; Searching a closed-loop vehicle sequence with negative reduced cost in the searching subgraph for any searching subgraph, and taking a freight vehicle combination represented by the closed-loop vehicle sequence as a target change combination if the closed-loop vehicle sequence meets the time window constraint of each freight vehicle, wherein the reduced cost is calculated by the corresponding weight of each directed arc; If the closed-loop vehicle sequence with the reduced cost being negative is not found in the searching sub-graph, iteratively expanding and updating the resource state labels of all access paths in the searching sub-graph to obtain a target access path or a target conclusion that the closed-loop path does not exist; under the condition that the target access path is obtained, if the closed-loop vehicle sequence meets the time window constraint among all the freight vehicles, taking the freight vehicle combination represented by the target access path as a target change combination; And under the condition that the target conclusion is obtained, judging that the target change combination is not found in each change node.
5. The method of freight vehicle dispatch as defined in claim 4, wherein the step of locating a closed loop vehicle sequence of reduced cost in the search sub-graph further comprises at least one of: For any graph node in the searching subgraph, calculating the total change-hanging time length of the target freight vehicle corresponding to the graph node from the departure to the completion of the change-hanging operation, extracting each redundant freight vehicle with the total change-hanging time length exceeding the corresponding cut-off time length of the target freight vehicle, and removing the redundant node corresponding to each redundant freight vehicle from the searching subgraph to obtain a new searching subgraph; And calculating the total transportation time length of the target freight vehicle corresponding to each directed arc in the search subgraph for reaching the destination corresponding to the vehicle after the completion of the change operation, extracting redundant directed arcs with the total transportation time length exceeding the corresponding deadline of the vehicle, and removing the redundant directed arcs from the search subgraph to obtain a new search subgraph, wherein the target freight vehicle and the vehicle corresponding graph nodes are connected through the directed arcs.
6. The method of dispatching a freight vehicle of claim 4, wherein said step of finding a closed-loop vehicle sequence with reduced costs in said search sub-graph comprises: Adding each graph node into a first queue to be processed, and recording a first path state from a first preset node to a path corresponding to each graph node, wherein the first path state comprises a first accumulated reduced cost, a first accessed node set and a first path starting time; Sequentially taking out graph nodes from the first queue to be processed as target nodes, expanding the target nodes to each first subsequent node to obtain a new path, and respectively calculating the path cost and the path time of the new path based on the first accumulated reduced cost and the first path starting time to obtain the path state of the new path, wherein the first subsequent nodes are other graph nodes except the accessed node set in the search subgraph; if the path state of the new path is better than all the history path states associated with the first subsequent node in the accumulated reduced cost, the accessed node set and the path starting time, updating all the history path states associated with the first subsequent node by using the path state of the new path, and adding the first subsequent node into the first queue to be processed; and returning to execute the step of sequentially taking out the graph nodes from the first waiting queue as target nodes until a closed-loop vehicle sequence with negative reduced cost or the first waiting queue is empty is detected.
7. The method of claim 4, wherein iteratively expanding and updating resource status labels for each access path in the search sub-graph comprises: Recording each initial label set of each graph node, and adding each node label in each initial label set into a second queue to be processed, wherein each node label comprises a second path state from a second preset starting node to a path corresponding to each graph node, and the second path state comprises a second accumulated reduced cost, a second accessed node set and a second path starting time; Extracting a node label with the minimum second accumulated reduction cost from the second queue to be processed as a label to be expanded, expanding the label to be expanded to a label corresponding to a second subsequent node, and generating a new label of the second subsequent node, wherein the second subsequent node is other graph nodes except the accessed node set in the searching subgraph; Adding a new label to the history label set if the new label of the second subsequent node is superior to the history label set associated with the second subsequent node in terms of accumulated reduced cost, accessed node set and path start time, removing each node label in the history label set, which is inferior to the new label in terms of accumulated reduced cost, accessed node set and path start time, and adding the new label to the second waiting queue; and returning to the step of extracting the node label with the smallest accumulated reduced cost from the second waiting queue as the label to be expanded until a second negative cost closed loop corresponding to the label to be expanded is detected or the second waiting queue is empty.
8. The method of freight vehicle scheduling of claim 1, wherein said step of converting said set of candidate change-over combinations into an optimal solution output that satisfies integer constraints comprises: Judging whether the corresponding solution of the candidate change-hanging combination set is an integer, wherein the candidate change-hanging combination set comprises various change-hanging combinations; Extracting a change relation in the solution corresponding to the candidate change combination set when the solution corresponding to the candidate change combination set is a non-integer, and taking the change relation as a branch object; Creating a first branch direction and a second branch direction for the branch object, wherein the first branch direction is used for forcing the change relation to occur, and the second branch direction is used for prohibiting the change relation from occurring; Constructing a new candidate change-hanging combination set based on a first constraint in the first branch direction, and constructing a new candidate change-hanging combination set based on a second constraint in the second branch direction, wherein the first constraint corresponds to the first branch direction, the second constraint corresponds to the second branch direction, the first constraint comprises the change-hanging relation for each change-hanging combination comprising the change-hanging relation and the change-hanging relation, and the second constraint comprises no change-hanging relation for each change-hanging combination; And executing the step of calculating the dual variable of the limited main problem based on the new candidate change hanging combination set until the corresponding solution of the candidate change hanging combination set is an integer, judging that the candidate change hanging combination set meets the integer constraint, and outputting the optimal solution corresponding to the candidate change hanging combination set.
9. A storage medium, characterized in that the storage medium is a computer-readable storage medium, on which a computer program is stored, which computer program, when being executed by a processor, carries out the steps of the method for scheduling a freight vehicle according to any one of claims 1 to 8.
10. A computer program product, characterized in that the computer program product comprises a computer program which, when executed by a processor, implements the steps of the method for scheduling a freight vehicle according to any one of claims 1 to 8.

Description

Method for dispatching freight vehicles, storage medium and computer program product Technical Field The present application relates to the field of scheduling optimization technology, and in particular, to a method, a storage medium, and a computer program product for scheduling a freight vehicle. Background With the continuous expansion of the scale of logistics industry and the increasing demand of highway freight, how to improve the transportation efficiency, reduce the operation cost and reduce the energy consumption by fine scheduling has become a key subject of industry development. In the existing freight dispatching scheme, road freight mainly depends on a point-to-point independent transportation mode, and after a single transportation task is completed, a vehicle often needs to return to a free travel or wait for a new task, so that the actual load rate of the vehicle is low, the free travel mileage is high, and the transport capacity waste and the cost rise are caused. Although digital freight platforms are becoming popular in recent years, some technologies attempt to optimize a single vehicle driving route through information sharing and path planning, but are still limited to local improvement of independent transportation tasks, and dynamic coordination and resource sharing of multiple vehicles in the transportation process cannot be achieved. Therefore, the existing freight dispatching scheme has the problem of poor dispatching effect. The foregoing is provided merely for the purpose of facilitating understanding of the technical solutions of the present application and is not intended to represent an admission that the foregoing is prior art. Disclosure of Invention The application mainly aims to provide a freight vehicle dispatching method, a storage medium and a computer program product, which aim to solve the technical problem of poor dispatching effect in the existing freight dispatching scheme. In order to achieve the above object, the present application provides a method for dispatching a freight vehicle, comprising: constructing a candidate change-hanging combination set based on received freight vehicle dispatching data, wherein the freight vehicle dispatching data at least comprises change-hanging nodes for changing and hanging all freight vehicles; Calculating a dual variable of the limited main problem corresponding to the candidate change-hanging combination set, and searching a target change-hanging combination in each change-hanging node based on the dual variable; under the condition that a target change combination is found in each change-hanging node, adding the target change-hanging combination into the candidate change-hanging combination set to obtain a new candidate change-hanging combination set, wherein the total cost of the new candidate change-hanging combination set is smaller than that of the candidate change-hanging combination set; And executing the step of calculating the dual variable of the limited main problem based on the new candidate change-hanging combination set, and converting the candidate change-hanging combination set into an optimal solution output meeting integer constraint under the condition that the target change-hanging combination is not found in each change-hanging node. In one embodiment, the step of constructing the candidate set of change-over combinations based on the received freight vehicle dispatch data comprises: Receiving freight vehicle dispatching data, wherein the freight vehicle dispatching data also comprises transport tasks corresponding to all freight vehicles; determining an independent transport combination for each of the freight vehicles to independently complete an associated transport task based on the freight vehicle scheduling data; Determining a feasible hanger changing combination of the hanger changing between every two freight vehicles based on the freight vehicle dispatching data, wherein the feasible hanger changing combination meets the time sequence constraint between the freight vehicles; integrating the independent transportation combination and the feasible hanging combination into a candidate hanging combination set, wherein each freight vehicle in the candidate hanging combination set is at least covered by one candidate hanging combination, and the candidate hanging combination comprises the independent transportation combination and the feasible hanging combination. In one embodiment, the step of calculating the dual variables of the candidate set of change-hanging combinations corresponding to the restricted main question includes: constructing a limited main question based on the candidate change-hanging combination set; And solving the limited main problem based on a preset linear programming solver, and extracting the dual variables of each freight vehicle from the output of the preset linear programming solver when the optimal solution of the total cost is obtained, wherein the dual variables cor