# US 2022/0035374 A1 · Scheduling method and system for fully autonomous waterborne inter terminal transportation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035374 A1
- Document ID: US20220035374A1
- Status: Published application
- Kind: A1
- Application number: 17/408,480
- Filed: 2021-08-22
- Published: 2022-02-03
- Earliest claimed: 2020-07-29
- Assignees: Zhejiang University
- Applicants: Zhejiang University
- Inventors: Huarong ZHENG; Wen XU; Dongfang MA; Fengzhong QU
- Web page: https://patentgrep.com/patent/US20220035374A1

## CPC

- G05D 1/69: Coordinated control of the position or course of two or more vehicles
- B63B 79/20: using models or simulation, e.g. statistical models or stochastic models
- B63B 79/40: for controlling the operation of vessels, e.g. monitoring their speed, routing or maintenance schedules
- G05B 17/02: electric
- G05D 1/228: Command input arrangements located on-board unmanned vehicles
- G05D 1/692: involving a plurality of disparate vehicles
- G08G 3/00: Traffic control systems for marine craft (marking of navigational route B63B22/16, B63B51/00)
- B63B 2035/007: {autonomously operating}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- B63B: SHIPS OR OTHER WATERBORNE VESSELS; EQUIPMENT FOR SHIPPING (arrangements of vessel ventilation, heating, cooling, or air-conditioning B63J2/00; floating substructures as supports of dredgers or soil-shifting machines E02F9/06)
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

The present application discloses is a scheduling method and system for fully autonomous waterborne inter terminal transportation, and belongs to the field of transportation. The method includes: establishing a dynamic scheduling model for waterborne Autonomous guided vessels (wAGVs); quickly inserting the dynamically arriving transportation tasks into all the existing wAGV paths, calculating the insertion cost and selecting the path and position with the lowest insertion cost to obtain updated initial paths; improving the initial path using a heuristic algorithm based on tabu search to obtain quasi-optimal wAGV paths; executing the scheduling wAGV paths. The scheduling model of the present application is based on the combinatorial optimization, and considers performance indexes such as transportation distance and customer satisfaction, and constraints such as time window and loading capacity. An initial path by using an insertion method within the framework of rolling horizon is constructed. The initial path is then optimized and improved by designing a tabu search heuristic so that obtaining quasi-optimal multi-wAGV paths are obtained in real time. This system is helpful to improve the autonomy level of large ports.

## Claims

### Claim 1

A scheduling method for fully autonomous waterborne inter terminal transportation, comprising the following steps:
1) modeling against a fully autonomous waterborne inter terminal transportation scheduling problem, establishing a waterborne autonomous guided vessel (wAGV) oriented mixed integer programming dynamic scheduling model, and solving the mixed integer programming dynamic scheduling model to obtain a starting optimal path for a scheduling system;
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 paths and positions that are with the minimum cost, inserting the task into the path, processing all the newly arrived transportation tasks in turn and obtaining updated initial paths;
3) based on the updated initial paths, using a heuristic algorithm based on tabu search to further improve the initial path, and solving to obtain a final scheduling scheme at the current time step, wherein the final scheduling scheme is 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;
4) scheduling the wAGVs according to the paths of all the wAGVs obtained by the solution, and repeating steps 2) to 4) for each new time step.

### Claim 2 (depends on 1)

The method for the fully autonomous waterborne inter terminal transportation scheduling according to claim 1, wherein
performance indexes of the dynamic scheduling model are as follows:
min c1Σv∈VxijvDij+c2∥w∥1+c3∥d∥1 (1),
where c1, c2 and c3 are weight coefficients of the three performance indexes in the model, wherein the first item minimizes the total driving distance, and the second item and the third item minimize the waiting time and the delay time, respectively; xijv(k) is integer binary variable with value of 0 or −1; for all (i,j)∈(k), v∈V, if wAGV v travles from node i to node j, then xijv(k)=1, otherwise xijv(k)=0; V is a fleet set with nv wAGVs; Dij is the waterway distance between the nodes i and j; vector w=[wit], i∈(k), where wit represents the waiting time at the node i; vector d=[dit], i∈(k), where dit represents the delay time at the node i; ∥⋅∥1 represents a 1 norm; (k) is a node set of an inter terminal scheduling transport network, and (k) is an edge set of the inter terminal scheduling transport network.

### Claim 3 (depends on 2)

The method for the fully autonomous waterborne inter terminal transportation scheduling according to claim 2, wherein
constraints of the dynamic scheduling model comprise:
Σv∈Vziv=1,∀i∈ (2)
ziv=z(i+n)v,∀i∈,v∈V, (3)
zii=1,∀i∈Vo, (4)
ziv=1,∀i∈′(k),v∈Vd, (5)
xijv=xijv=ziv,∀i∈v∈V, (6)
xvjv=1,∀v∈V, (7)
xi(nv+2n(k)+nd+v)v=1∀v∈V, (8)
Av=kTs,∀v∈Vw, (9)
Ai≤Ai+n,∀i∈n, (10)
x
i
⁢
j
⁢
v
⁡
(
k
)
=
1
→
max
⁡
(
A
i
,
t
i
,
min
)
+
s
i
+
d
i
⁢
j
u
=
A
j
,
∀
(
i
,
j
)
∈
⁢
,
v
∈
𝒱
,
(
11
)
ti,min−wi≤Ai≤ti,max−si+di,∀i∈, (12)
0≤wi≤wmax,∈i∈, (13)
0≤di≤dmax,∀i∈, (14)
yv0=lv,∀v∈V, (15)
xijv(k)=1→yi+qi=yj,∀i∈,v∈V, (16)
0≤yj≤Q,∀i∈, (17)
xijv,ziv∈{0,1}, (18)
where ziv(k) is an integer variable from 0 to 1; for all i∈(k), v∈V, if a wAGV v visits the node i, then ziv(k)=1, otherwise ziv(k)=0; Vo(k)={1, . . . , nv} is defined as a starting node set of all the wAGVs, and Ve(k)={nv+2n(k)+nd+1, . . . , 2nv+2n(k)+nd} is defined as an ending node set of all the wAGVs; wherein n(k)=Ev∈V|Rvp(k)|+|Rnew(k)| is a number of pickup and delivery tasks, and nd is a number of delivery-only tasks; all pick-up nodes are defined as (k)={nv+1, . . . , nv+n(k)}, delivery nodes corresponding to the pick-up nodes are defined as (k)={nv+n(k)+1, . . . , nv+2n(k)}, and the delivery-only nodes are defined as ′(k)={nv+2n(k)+1, . . . , nv+2n(k)+nd(k)}, in which u is a cruising speed of the wAGV, Ts is a step length of the time step, k is a discrete time step serial number, Ai represents the time arriving at the node i, yi is a number of containers loaded on the wAGV arrived at the node i, si is a required terminal service time, ti,min, ti,max are an earliest pickup time and a latest delivery time, respectively; Q is a maximum loading capacity of the wAGV, a subscript max indicates a maximum allowable value of corresponding physical quantity, and a subscript min indicates a minimum allowable value of the corresponding physical quantity.

### Claim 4 (depends on 1)

The method for the fully autonomous waterborne inter terminal transportation scheduling according to claim 1, wherein the step of inserting a newly arrived transportation task into possible positions in all existing paths of the wAGVs, and calculating an insertion cost according to a path calculated in the previous step but has not been completely executed under a rolling horizon framework comprises:
for all the wAGVs, defining an incomplete path thereof as (k)={r1, . . . , rm}, where ri,ri, i=1, . . . , m is a node to be visited in a previous plan of the wAGV v, and may be an empty set; assuming that the newly arrived transportation task is pi, di, inserting the task into all possible positions in the existing paths of the wAGVs, and calculating the insertion cost; for the pick-up node pi, inserting the task into an edge ri,rj of a certain path (k); if neither the capacity nor the time window constraints are violated, calculating the insertion cost as:
Δdp=dripi+dpiri−drirj,
where dripi represents a distance from the node ri to the node pi; sorting the costs of all possible insertion positions of the pick-up node pi in an ascending order, and then starting from the smallest Δdp, inserting, in a similar way, the delivery node di into the possible positions which do not violate the capacity and the time window constraints after the corresponding picking node pi, and calculating the insertion cost of the delivery node di as Δdd; selecting a minimum Δdd value and the current corresponding Δdp, then the cost of inserting the new task pi, di into the path being Δdp+Δdd; sequentially calculating the cost of inserting pi, di into current paths of all wAGVs and selecting the paths and positions corresponding to the selected minimal cost value, and inserting the task to update the path; processing all newly arrived transportation tasks in turn according to an arrival time sequence.

### Claim 5 (depends on 1)

The method for the fully autonomous waterborne inter terminal transportation scheduling according to claim 1, wherein the step 3) comprises:
3.1) designing a neighborhood space of the current solution;
3.2) defining two matrices to store neighborhood search and iterative information; first, defining an n×n-dimensional matrix, where n≤nv, which stores optimal solution information obtained after neighborhood transformation between any two path pairs and a sequence number of the path pair, wherein the sequence number is a row sequence number of a defined second matrix; the second matrix stores neighborhood transformation information of the corresponding path pair, including ID of two path involved in the transformation, the number of tasks transformed in the two paths and the positions in the path;
3.3) defining a tabu table, 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 the iteration from falling into a loop;
3.4) 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 is noted that each iteration only needs to update the matrix information corresponding to the path with neighborhood transformation in the matrix, rather than update the matrices of all paths;
3.5) repeating the above steps from 3.1) to 3.4) for iteration, and gradually improving the quality of the scheduling scheme to approximate optimum through continuous neighborhood change and path update; wherein the final scheduling scheme is the paths of all the wAGVs, including the sequence of terminal nodes to be visited, the corresponding visit time, staying time and the number of loaded and unloaded cargoes.

### Claim 6 (depends on 5)

The method for the fully autonomous waterborne inter terminal transportation scheduling according to claim 5, wherein the step 3.1) comprises:
designing two kinds of neighborhood spaces, wherein the first structure is to arbitrarily select any group of pick-up and delivery nodes in one of the two paths in the existing solution, first delete the pick-up and delivery nodes from the initial route, and then insert them into the other path; before inserting another path, it is necessary to detect whether the capacity constraint is satisfied, and the waiting time or the delay time generated due to the time window constraint is used for calculating the insertion cost along with the driving distance according to the weight in the dynamic scheduling model;
the second neighborhood structure is to exchange a group of pick-up and delivery nodes in two arbitrarily selected paths, that is, selecting pick-up and delivery node pairs from the two paths first, and then deleting from the initial route, and then inserting the pick-up and delivery node pairs into another path; before inserting another path, it is necessary to check whether the capacity constraint is satisfied, and the waiting time or the delay time generated due to the time window constraint is used for calculating the insertion cost along with the driving distance according to the weight in the dynamic scheduling model.

### Claim 7

A system for fully autonomous waterborne inter terminal transportation scheduling, comprising a waterborne autonomous guided vessel (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; wherein
the wAGV system comprises a number of wAGVs which are controlled by the scheduling module to execute transportation tasks;
the initial path solving module of the dynamic scheduling model is configured 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;
the initial path construction module is configured for inserting new transportation tasks into the possible positions in all the existing wAGV paths according to the paths calculated in a previous step but has not been completely executed within a rolling horizon framework, calculating the insertion cost and selects paths and corresponding positions with the lowest insertion cost, selecting the paths and positions corresponding to the minimum cost, inserting the task into updated paths, and sequentially processing all new transportation tasks and obtaining updated initial paths;
the real-time optimization module is configured by adopting a heuristic algorithm based on tabu search, combining 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 realizing the real-time scheduling system; and
the scheduling module is configured for controlling, according to the scheduling result according to the paths of all wAGVs in the current rolling horizon step obtained by the real-time optimization module, the wAGVs to visit specific terminals at specific times according to the scheduling result according to the paths of all wAGVs in the current rolling horizon framework obtained by the real-time optimization module, 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.
