SCHEDULING METHOD AND SYSTEM FOR FULLY AUTONOMOUS WATERBORNE INTER TERMINAL TRANSPORTATION

Description

BRIEF DESCRIPTION OF DRAWINGS

[0021] FIG. 1 is a schematic diagram of a dynamic planning path for a wAGV;

[0022] in which, 1, Container terminal, 2, Waterway node, 3, Planned completed path, 4, Planned but uncompleted path, 5,1 TEU container, 6, wAGV.

[0023] FIG. 2 is a schematic diagram of the neighborhood of the select-insert action;

[0024] FIG. 3 is a schematic diagram of the neighborhood of an exchange action;

[0025] FIG. 4 is a planned path at time step k=7;

[0026] FIG. 5 is a planned path at time step k=8;

[0027] FIG. 6 shows a diagram of travel-distance/terminal ID vs. time of waterborne AGV 2;

[0028] FIG. 7 shows the loads on board waterborne AGVs;

[0029] FIG. 8 is a diagram showing the satisfaction of request time windows.

DESCRIPTION OF EMBODIMENTS

[0030] The present application will be further illustrated and explained with reference to specific embodiments. Technical features of various embodiments of the present application can be combined accordingly without conflicting with each other.

[0031] According to the method, the problem of dynamic scheduling of waterway transportation among large port terminals is considered, and the nodes and time series of taking a specific number of containers from a specific terminal and transporting them to a destination terminal within a certain time window are determined. The overall goal is to complete the transportation tasks among all terminals, and at the same time, wAGVs have the shortest driving distances, the shortest waiting times and the shortest delay times at the terminals.

[0032] FIG. 1 is a schematic diagram of a dynamic planned path for a wAGV. Because the planned transportation tasks may not be finished at the new decision time step, the scheduling decision at the new decision time step needs to consider both the previous uncompleted tasks and the newly arrived transportation tasks.

[0033] Based on the above scheduling decision requirements, this embodiment provides a scheduling method for fully autonomous waterborne inter terminal transportation, which mainly includes the following steps:

[0034] 1) modeling against a fully autonomous waterborne inter terminal transportation scheduling problem, establishing a wAGV-oriented mixed integer programming dynamic scheduling model, and solving the mixed integer programming problem to obtain a starting optimal path of the scheduling system;

[0035] 2) inserting a newly arrived transportation task into the possible positions in all the existing paths of wAGVs calculated in the previous step but has not been completely executed within a rolling horizon framework, and calculating the corresponding insertion cost, comparing and selecting the paths and positions that are with the minimal cost, inserting the task into the path, processing all the newly arrived transportation tasks in turn and obtaining updated initial paths;

[0036] 3) based on the updated initial paths, using a heuristic algorithm based on tabu search to further improve the initial path, and obtaining a final scheduling scheme at the current time step, wherein the final scheduling scheme consist of paths of all the wAGVs; the paths of all the wAGVs include terminal node sequences to be visited by all the wAGVs, corresponding visiting times, service times and the number of loading and unloading containers in TEUs;

[0037] 4) scheduling the wAGVs according to the paths of all the wAGVs obtained by the solution, and repeating steps 2)-4) for each new time step.

[0038] It can be seen from the steps of the method of the present application that a dynamic scheduling model is proposed firstly. In this embodiment, the model is a dynamic scheduling mathematical model based on rolling horizons and mixed integer programming. By solving this model, the initial optimized path of the scheduling system is obtained (the modeling and model solving of the present application can occur at any time or time step in the actual transportation scheduling process, and the time of model solving is taken as the initial time step of the method of the present application). After the initial optimized path is obtained, the real-time performance of the scheduling system is considered. For the newly arrived transportation, it needs to be inserted into the existing path, and a new optimized scheduling scheme is obtained by considering constraints and insertion costs. Therefore, according to the present application, an initial path construction method combining a rolling horizon, an insertion method and a path improvement solving algorithm based on tabu search are further provided, so that a final scheduling scheme under the current time step can be obtained, and the final scheduling scheme consist of the paths of all wAGVs in the system; the paths of all wAGVs in the system include terminal node sequences to be visited by all wAGVs, corresponding visiting time, staying time and number of loaded and unloaded cargoes. For the next time step, the initial path construction method combined with the rolling horizon and insertion method, and the improved path heuristic algorithm based on tabu search, which are proposed by the present application, are repeatedly executed considering the path calculated in the previous step and the newly arrived transportation task within the rolling horizon framework, thus completing the full autonomous waterborne inter terminal transportation scheduling in the whole time range.

[0039] Each part of the present application will be further explained below.

[0040] I. Dynamic Scheduling Based on Rolling Horizon and Mixed Integer Programming

[0041] First, the parameters involved in the mathematical model of the scheduling problem are defined. We consider, a time range t∈[0, ∞], a dynamic transportation system with a fleet of n.sub.v wAGVs denoted by V, where the wAGV set executing the tasks is V.sub.w. The re-scheduling is performed with an interval T.sub.s, and the discrete planning time step is defined as k, then t=kT.sub.s.

[0042] At each time step k, the tasks unfinished R.sub.v(k)=R.sub.v.sup.p (k)∪R.sub.v.sup.d(k), ∀v∈Vand the newly arrived task R.sub.new(k) at [(k+N.sub.p−1)T.sub.s, (k+N.sub.p)T.sub.s] are considered, and the re-scheduling problem is established in the time horizon [kT.sub.s, (k+N.sub.p)T.sub.s], where R.sub.v.sup.p(k) are the tasks that have not yet commenced by kT.sub.s, and R.sub.v.sup.d(k) are the tasks for which the container have already been placed on the wAGV v for delivery to the destination terminal.

[0043] At the next time step k+1, the scheduling process is repeated and the tasks in the next N.sub.p time steps are considered, thus accounting for the term “rolling horizon”. At the same time, the number of containers on each wAGV can be calculated as l.sub.v(k)≤Q, where Q is the maximum capacity of the wAGV. The real-time position of the wAGV is recorded as (x.sub.v(k), y.sub.v(k)), the corresponding waterway section is recorded as g.sub.v(k), and the remaining time of staying/serving at the current point is s.sub.v(k). Therefore, the dynamic system state of the wAGV can be expressed (x.sub.v (k), y.sub.v(k), g.sub.v(k), s.sub.v(k), l.sub.v (k), R.sub.v(k)),∀v∈V. The cruising speed of the wAGV is u.

[0044] Accordingly, for each transportation task i E U.sub.v6531v R.sub.v(k) U R.sub.new(k), it can be expressed by (i, p.sub.i, d.sub.i, t.sub.i,min, t.sub.i,max q.sub.i, s.sub.i) which represent the task number, the pickup terminal, the delivery terminal, the earliest pickup time, the latest delivery time, the number of containers, and the required terminal service time, respectively. For the pickup terminal p.sub.i, q.sub.i>0; for the delivery terminal d.sub.i, q.sub.i<0.

[0045] The waterway transportation network between terminals is modeled. V.sub.o(k)={1, . . . , n.sub.v} is defined as the starting node set for all wAGVs and V.sub.e(k)={n.sub.v+2n(k)+n.sub.d(k)+1, . . . , 2n.sub.v+2n(k)+n.sub.d(k)} as the ending node set for all wAGVs, where Σ.sub.v∈V|R.sub.v.sup.p(k)|+|R.sub.new(k)| is the number of pick-up and delivered transportation tasks, and n.sub.d(k) is the number of delivery-only tasks. All pick-up nodes are defined as (k)={n.sub.v+1, . . . , n.sub.v+n(k)} and the delivery nodes corresponding to the pick-up nodes are (k)={n.sub.v+n(k)+1, . . . , n.sub.v+2n(k)} and the delivery-only nodes are ′(k)={n.sub.v+2n(k)+1, . . . , n.sub.v+2n(k)+n.sub.d(k)}. Therefore, the transportation network considered for the inter-terminal scheduling problem is (k)=(T (k), (k)), where the node set is f(k)=(k)∪(k)∪′(k)∪V.sub.o(k)∪V.sub.e(k), and the edge set is

(k)={(i,j)|

(i,j)∈((k)∪(k)∪′(k))×((k)∪(k)∪′(k)))

∪{(i,j)|i∈V.sub.o(k),j∈(k)∪(k)∪′(k)}

∪{(i,j)|i∈(k),∪(k)∪′(k,j∈V.sub.o(k)},i≠j}.

[0046] The following decision variables are defined:

[0047] 0-1 binary variable x.sub.ijv(k) for all i, j) ∈(k), v∈V, if the wAGV v tavels from node i.fwdarw.j, then x.sub.ijv(k)=1, otherwise x.sub.ijv(k)=0;

[0048] 0-1 binary variable z.sub.iv(k) for all i∈(k), v∈V, if the wAGV v visits the node i, then z.sub.iv(k)=1, otherwise z.sub.iv(k)=0;

[0049] the integer variable y.sub.i(k) for all i∈(k) represents the number of containers loaded on the wAGV arriving at the node i;

[0050] the continuous variable A.sub.i(k) for all i∈(k) represents the time to reach the node i;

[0051] the continuous variable w.sub.i.sup.t(k) for all i∈(k) represents the waiting time at the node i;

[0052] the continuous variable d.sub.i.sup.t(k) for all i∈(k) represents the delay time at the node i;

[0053] For simplicity of description, ⋅ (k) in the dynamic parameters will be omitted below. After these parameters are defined, a mixed integer programming model is established to model the scheduling problem.

min c.sub.1Σ.sub.v∈V(x.sub.ijvd.sub.ij+c.sub.2∥w∥.sub.1+c.sub.3∥d∥.sub.1  (1)

[0054] subject to

Σ.sub.v∈Vz.sub.iv=1,∀i∈  (2)

z.sub.iv=z.sub.(i+n)v,∀i∈,v∈V,  (3)

z.sub.ii=1,∀i∈V.sub.o,  (4)

z.sub.iv=1,∀i∈′(k),v∈V.sub.d,  (5)

x.sub.ijv=x.sub.ijv=z.sub.iv,∀i∈v∈V,  (6)

x.sub.vjv=1,∀v∈V,  (7)

x.sub.i(n.sub.v.sub.+2n(k)+n.sub.d.sub.+v)v=1∀v∈V,  (8)

A.sub.v=kT.sub.s,∀v∈V.sub.w,  (9)

A.sub.i≤A.sub.i+n,∀i∈.sub.n,  (10)

[00001]$\begin{array}{cc}{x}_{ijv}\left(k\right)=1.fwdarw.\max \left(A_i,t_{i,\min }\right)+s_i+\frac{d_{ij}}{u}=A_j,\forall \left(i,j\right)\in ,v\in \mathrm{��},& \left(11\right)\end{array}$
t.sub.i,min−w.sub.i≤A.sub.i≤t.sub.i,max−s.sub.i+d.sub.i,∀i∈,  (12)

0≤w.sub.i≤w.sub.max,∈i∈,  (13)

0≤d.sub.i≤d.sub.max,∀i∈,  (14)

y.sub.v.sub.0=l.sub.v,∀v∈V,  (15)

x.sub.ijv(k)=1.fwdarw.y.sub.i+q.sub.i=y.sub.j,∀i∈,v∈V,  (16)

0≤y.sub.j≤Q,∀i∈,  (17)

x.sub.ijv,z.sub.iv∈{0,1},  (18)

[0055] In formula (1), the first term minimizes the total travel distance, while the second term and the third term minimize the waiting time and the delay time, respectively. c.sub.1, c.sub.2 and c.sub.3 are the weight coefficients among them. Formulas (2)-(18) represent constraints such as consistency, time, capacity and 0-1 integer variable, respectively. Specifically, formula (2) constrains each node is visited by one and only one wAGV, and formula (3) defines for each pair of pick-up and delivery nodes, the pick-up node is visited before the delivery node and is visited by the same wAGV. Formulas (4) and (5) ensure that the wAGV will visit the starting node and the ending node with containers. Formula (6) means that the wAGV will only enter and exit a certain node if it visits that node. Formulas (7) and (8) constrain the wAGV to start and end at correct nodes. Formula (9) constrains the time consistency of the wAGVs that are executing tasks. Formula (10) ensures delivery after picking up. Formula (11) constrains the time consistency between adjacent visited nodes. Formulas (12)-(14) define time window constraints. The capacity constraints are defined by formulas (15)-(17). The 0-1 integer variable is defined by formula (18).

[0056] Because the problem defined by formulas (1)-(18) is a complex combinatorial optimization problem, it is used to solve the starting path when the number of transportation tasks at the first step is small in the actual scheduling system. The modeling and model solution of the present application can take place at any time or time step (preferably the initial stage when the number of transportation tasks is small) in the actual transportation scheduling process. The present application takes the starting time as the initial time step of the present method, and further proposes an efficient real-time solution algorithm (heuristic real-time solution algorithm) for the situation that transportation tasks come in real time, and a large number of transportation tasks need to be handled in subsequent time steps.

[0057] II. Real-Time Heuristic Solution Algorithm

[0058] Firstly, according to the path calculated in the previous step but has not been completely executed in the rolling horizon framework, the newly arrived task is inserted according to certain rules, and an initial planned path is obtained.

[0059] For all the wAGVs, the incomplete path thereof is defined as (k)={r.sub.1, . . . , r.sub.m}, where r.sub.i, r.sub.i, i=m is a node to be visited in the previous plan by wAGV v. Note (k) may be an empty set. If the newly arrived transportation task is <p.sub.i, d.sub.i>, the cost of inserting this task into all possible positions in the existing paths of the wAGV will be calculated once, and these insertion positions need to meet the constraints such as time window, capacity, pick-up followed by delivery and non-transshipment. For the pick-up node p.sub.i, the task is inserted into an edge r.sub.i,r.sub.j of a certain path (k); if neither the capacity nor the time window constraints are violated, calculating the insertion cost as:

Δd.sub.p=d.sub.r.sub.i.sub.p.sub.i+d.sub.p.sub.i.sub.r.sub.j−d.sub.r.sub.i.sub.r.sub.j

[0060] The costs of all possible insertion positions of the pick-up node p.sub.i are sorted in an ascending order, and then starting from the smallest Δd.sub.p, d.sub.i is inserted after the corresponding point p.sub.i in a similar way. The insertion cost of d.sub.i is calculated as Δd.sub.d for the position that does not violate the constraints. For d.sub.i, if it is detected that an insertion point violates the capacity constraint, the remaining insertion positions can be skipped. The minimum Δd.sub.d value and the current corresponding Δd.sub.p are found out, then the cost of inserting the new task p.sub.r, d.sub.i into the path (k) is Δd.sub.p+Δd.sub.d. The costs of inserting p.sub.r, d.sub.i into current paths of all wAGVs are sequentially calculated, and the paths and positions corresponding to the selected minimal cost value are selected, and the task is inserted to update the path. All newly arrived transportation tasks are processed in turn to obtain updated initial paths.

[0061] Based on the obtained initial path, tabu search is used to improve it. Tabu search is a kind of neighborhood search. However, there are two main differences between its search rules and other neighborhood search methods. First, during iterations, it allows the incumbent solution to be temporarily inferior to the current best solution, thus avoiding falling into the local optimal solution. Secondly, tabu search defines a tabu data structure to memorize the most recently executed actions, so that only the actions not in this memory structure can be executed in the future, so as to avoid iteration falling into an infinite loop. When the incumbent solution is better than the global optimal solution, this tabu action can also be forgiven.

[0062] Firstly, the neighborhood space of the current solution is designed. Because of constraints such as pickup followed by delivering and no transshipment, it is necessary to consider the simultaneous movement of the pick-up node and the delivery node when designing the neighborhood.

[0063] Two kinds of neighborhoods are designed. The first one is to arbitrarily select any group of pick-up and delivery nodes in two of the paths in the existing solution, delete the pick-up and delivery nodes from the initial route first, and then insert them into the other path, as shown in FIG. 2. Different from the previous new task insertion, only the capacity constraint needs to be strictly met, and the time window constraint is similar to formula (1), which only involves penalty for the waiting time and the delay time, but does not need to be strictly met.

[0064] The second neighborhood structure is to exchange a group of pick-up and delivery nodes in two arbitrarily selected paths, that is, pick-up and delivery node pairs are selected from two paths first, and then are deleted from the initial route, and then the pick-up and delivery node pairs are inserted into another path, as shown in FIG. 3. Similarly, the capacity constraint needs to be strictly met, and the time window constraint takes the way of penalty in the cost function.

[0065] Based on the designed neighborhoods, two matrices are defined to store neighborhood search and iteration information. At first, an n×n (n≤n.sub.v) dimensional matrix is defined to store the optimal solution information obtained by neighborhood transformation between any two path pairs and the sequence number of the path pair, wherein the sequence number is a row sequence number of a defined second matrix. The second matrix stores the information of two interchanged routes, including the IDs of the routes, positions in the routes and number of tasks, etc. By this structure, in each iteration, we only need to update the matrix information that is related to the changed routes in the previous iteration instead of all paths. At the same time, a tabu table is defined, wherein the tabu table comprises tabu objects and tabu lengths. The tabu objects are defined as a transportation task ID and a path ID, and the tabu length is positioned as a sum of a number of current iteration steps and a preset number of steps of tabu release, and when the number of iteration steps is less than the tabu length, the transportation tasks in the tabu objects cannot be inserted into the corresponding path, so as to avoid iteration falling into a loop. In each iteration, selecting the neighborhood transformation with the most cost reduction; if the transformed cost value is smaller than the current recorded minimum cost value and the transformation is not in the tabu table, recording the cost value as the minimum cost value and updating the path; it shall be noted that each iteration only needs to update the matrix information corresponding to the path with neighborhood transformation in the matrix, and does not need to update the matrices of all paths. The above steps are repeated for iteration, and the quality of the scheduling scheme is gradually improved to be quasi-optimal through continuous neighborhood change and path update; wherein the final scheduling scheme is the paths of all wAGVs, including the sequence of terminal nodes to be visited, the corresponding arrival times, stopping times and the number of loaded and unloaded cargoes.

[0066] The system for the fully autonomous waterborne inter terminal transportation scheduling according to the present application includes a wAGV system, an initial path solving module of a dynamic scheduling model, an initial path construction module, a real-time optimization module and a scheduling module.

[0067] The wAGV system comprises a number of wAGVs, which are controlled by the scheduling module to execute transportation tasks.

[0068] The initial path solving module of the dynamic scheduling model is used for acquiring parameters involved in defining the dynamic scheduling model, establishing the dynamic scheduling model, determining constraints of the model and acquiring a first initial scheduling path of the scheduling system.

[0069] The initial path construction module inserts new transportation tasks into the possible positions in all the existing wAGV paths according to the paths calculated in the previous step but has not been completely executed within a rolling horizon framework, calculates the insertion cost and selects paths and corresponding positions with the lowest insertion cost, selects the paths and positions corresponding to the minimum cost, inserts the task into updated paths, and sequentially processes all new transportation tasks and obtains updated initial paths.

[0070] The real-time optimization module adopts a heuristic algorithm based on tabu search, combines the initial paths obtained by the initial path construction module and constraints of the dynamic scheduling model to obtain a quasi-optimal scheduling result within the rolling horizon framework, and realizes the real-time scheduling system.

[0071] The scheduling module is used for controlling, according to the scheduled paths obtained by the real-time optimization module, the wAGVs to visit specific terminals at specific times, picking up or unloading a specific number of containers, and completing the assigned transportation task in an approximately shortest driving path, with the minimum waiting time and delay time.

[0072] In order to verify the effectiveness of the proposed algorithm, a simulation experiment is carried out using the data of multi-terminal transportation in the port of Rotterdam.

[0073] The number of the wAGVs is 8, T.sub.s=15 min., N.sub.p=4, i.e., the scheduling time domain to 1 hour. FIG. 4 and FIG. 5 show the planned path of one of the wAGVs for two consecutive time steps k=7 and k=8. The small rectangle on the path indicates 1 TEU, and the number above indicates the transport task number to which the container belongs. FIGS. 4 and 5 contain the planned results of this time step: the ID of the terminal to be visited, the arrival and departure times, and the number of containers to be loaded and unloaded. For example, in FIG. 4, when the wAGV leaves the terminal 6, there are 2 containers of the task 9 and 2 containers of the task 18; next, the wAGV arrives the terminal 8, then the two containers of the task 18 are unloaded first, and then the two containers of the task 21 are loaded. Loading and unloading operations at the same terminal are often carried out together to reduce the total distance traveled. Comparing the planned paths for k=7 and k=8, it can be seen that newly arriving tasks 23 and 26 are inserted into the path for k=7. The operations that happen at the same terminal node are integrated to reduce the driving distance.

[0074] FIG. 6 shows the accumulation of traveling distance of one of the wAGVs over time, and the visited terminal is also marked in the figure. Whenever the wAGV arrives at a terminal, it will stay for a period of time to complete the loading and unloading operation. The reason for the wAGV to stay for different periods of time at different terminals is that loading and unloading operations of multiple tasks need to be carried out at certain terminals, or the wAGV needs to wait for the start of tasks at that terminal.

[0075] As the wAGV has the maximum capacity limit, the number of containers on board all eight wAGVs in the whole simulation period is given in FIG. 7. It can be seen that all wAGVs are not overloaded, that is, the number of containers has never exceeded the upper limit of the capacity of 4 TEU.

[0076] For the time window constraint, the set time difference of all transportation tasks and the time required for task time completion are shown in FIG. 8. All tasks are completed within the time window, which also shows the effectiveness of the scheduling algorithm.

[0077] The above examples only express several embodiments of the present application, and their descriptions are specific and detailed, but they cannot be understood as limiting the scope of the patent of the present application. It should be pointed out that, for those of ordinary skill in the field, without departing from the concept of the present application, several modifications and improvements can be made, which belong to the protection scope of the present application. Therefore, the scope of protection of the patent of the present application shall be subject to the appended claims.