考慮倒箱操作的AutoStore魔方型倉儲系統自動引導車雙層路徑規劃

AutoStore系統是一種新興的緊致輕載倉儲系統[1,2],它取消巷道，將標準化貨格直接組合在一起，形成魔方型結構；用于存儲貨物的料箱規格統一，垂直堆存在每個貨格中。自動引導車(automated guided vehicle, AGV)在貨架頂層沿軌道移動，小車4個側面各設有一組輪子，能實現前后左右4個方向的移動和轉向，小車底部裝有伸縮抓取裝置。工作臺設置在貨架邊緣，當存儲或揀選任務產生時，由工作人員確定要存入或揀選的料箱，將指令發送至AGV管理系統。AGV接受到指令后，移動到目標箱位所在貨格頂部，伸縮臂伸入貨格將料箱抓取收入自己“腹”中，隨后帶著料箱移動到工作臺頂部，并通過抓取裝置將料箱放入工作臺通道。待工作人員存入或揀選完貨物后，調用AGV將料箱運回，至此，完成一次存儲或揀選工作。

從上述工作流程看，AGV為該“貨到人”系統的核心環節，對其進行研究能提高系統運行效率。AGV路徑規劃是生產調度領域的熱點問題，中外已有較多研究成果：從問題研究范疇上，可分為靜態調度、動態調度和聯合調度[3,4];從研究方法上，可分為數學建模方法、仿真優化、智能優化和混合優化等[5,6]。然而，AutoStore獨特的倉儲結構使得AGV路徑規劃問題與傳統研究有較大區別，主要體現在兩個方面：一方面，AutoStore系統中AGV在頂層軌道實現水平方向移動，底部伸縮裝置實現垂直方向移動，路徑規劃問題轉變為三維空間路徑尋優問題，傳統平面路徑尋優方法已不適用；另一方面， AutoStore系統中存在大量的倒箱操作，當目標箱不在貨格頂層時，AGV需要將其上部的阻礙箱依次搬開直至目標箱處于頂層。這使得AGV除了要完成搬運目標箱的工作外，還需完成相應的倒箱工作。而倒箱的次數和具體位置是可變的，即任務數不確定，增加了路徑規劃的復雜程度。

現階段針對AutoStore系統的研究大多關注生產線設計[7,8]、存儲策略[9,10]及貨位優化[11]。王曉軍等[12]認為存儲越深的目標箱需要倒箱的可能性越高，因此在AGV路徑規劃建模時將目標箱垂直提升時間乘以了一個系數，但該研究未考慮倒箱實際操作，本質上還是二維平面路徑尋優問題。

考慮到AutoStore系統的倒箱和集裝箱堆場倒箱(翻箱)操作有一定的相似處，文獻[13,14,15]進行了分析。堆場倒箱主要發生在提箱環節，需要根據目標箱位置及當前堆場的實時狀態來制定倒箱堆放策略。在倒箱限制及落箱位的選擇上，所研究的內容與堆場倒箱的不同之處如下。

(1)堆場倒箱操作大部分在單貝位內進行，少部分能在相鄰貝位進行，但在AutoStore系統中，AGV可帶著料箱在整個貨格頂層行走，落箱位置選擇范圍更大，造成倒箱規模復雜。

(2) AutoStore系統是具有自我調節能力的智能系統，產生倒箱操作的料箱不需再運回原處，慢慢地提取率高的料箱會處于貨架上層，而提取率低的料箱會沉入下層。

(3)AutoStore大多采用訂單批處理的策略，即一次需要提取多個目標箱，使得阻礙箱數量增多，且阻礙箱的落箱位置會相互影響，使得問題研究更為復雜。

考慮倒箱操作的AutoStore系統AGV路徑規劃需解決以下核心問題：一是建立適合該魔方型倉儲揀選系統的倒箱策略；二是如何對能在三維空間活動的AGV路徑問題進行建模和求解；三是倒箱和搬運都需要由AGV完成，如何將兩者結合起來。

基于上述分析，首先在工作流程基礎上對問題進行了界定，給出了建模方法及倒箱、提箱的作業規則；其次建立了AGV路徑規劃雙層模型，內層模型用于求解阻礙箱的倒箱路徑，以此為基礎，外層模型對多AGV路徑規劃問題進行了分析；然后基于模型特點提出了嵌套啟發式算法，最后通過算例對模型和算法進行了驗證和比較分析。

AGV的指令均由工作臺發出，根據目標箱與工作臺的相對位置，可分為“目標箱出庫”和“目標箱入庫”兩類指令。其中“目標箱出庫”指將目標箱搬運至工作臺，可分解成如下步驟。

步驟1 AGV接收任務，獲取目標箱及其上方阻礙箱的位置信息。

步驟2 從當前位置空駛至目標箱貨格頂層。

步驟3 依次搬運阻礙箱至相應落箱位，直到目標箱位于頂層。

步驟4 將目標箱搬運至工作臺。

步驟5 出庫指令完成，釋放AGV。

工作人員在工作臺對目標箱完成揀選或存儲操作后，發出“目標箱入庫”指令，調用最近的空閑AGV,將目標料箱搬運回貨架，為了保持貨架整體存儲平衡，存入最深可用的貨格。與“目標箱出庫”相比，目標箱入庫較為簡單，屬于起始位置確定且不涉及倒箱操作的AGV調用問題，用最短路徑尋優即可解決，因此，主要討論“目標箱出庫”這一階段。

在貨到人工作模式下，存儲和揀選的區別體現在工作人員對目標箱的操作及服務時間上，對AGV路徑規劃求解無本質影響，因此，將二者統一考慮。同時為與實際情況相符，設工作人員一次處理一批訂單，訂單內包含數個任務，但順序無先后約束。綜上，本問題可以簡述為：有一系列待提取目標箱，初始位置和終點位置(工作臺)確定，目標箱上面的阻礙箱數量及位置確定，有多個AGV,需要將阻礙箱倒箱及目標箱運輸任務分配給各AGV,并指定執行先后順序，選擇最優運行路徑。

AutoStore貨架呈魔方型結構，在傳統柵格法建模[16]基礎上，采用柵格法進行三維建模。以貨架左下角為坐標原點O,對行、列、層分別建立X、Y和Z軸。以料箱尺寸為基本單位，將貨架劃分成立體柵格，一個柵格代表一個箱位，用確定坐標(x,y,z)表示。

圖1給出了4×4×4規模貨架示意圖。設貨架所有箱位集合為M,根據箱位是否存放料箱又可分為兩個子集合：被料箱占用的實箱位集合M1,如箱位a(1,1,4)∈M1;沒被占用的空箱位集合M2,如箱位e(2,1,4)∈M2。

貨架建模完成后，在頂層坐標(Zmax+1)處建立虛擬柵格區作為AGV移動區，如AGV1當前坐標為(3,1,5),則移動路徑可以用一連串柵格坐標表示。AGV充電區設置貨格頂層外側，不影響貨格正常存儲，同時該區域也是路徑規劃的起始點和終點，如AGV2的坐標為(0,2,5)。工作臺設置在貨架外側，規模尺寸為兩個標準化貨格，上部為運輸通道，分為入庫通道和出庫通道，下部為人工操作臺。AGV將入庫目標箱放入入庫通道即可離去，目標箱在通道內排隊，按先到先服務原則接受服務。工作人員完成操作后，將目標箱推入出庫通道底部，依次調用AGV。

同一波次訂單達到后，首先對其進行匯總，將同類貨品歸類，獲得待揀貨品列表及其所需求數量?？紤]到料箱尺寸較小，設定每個料箱只存放一類貨品且不能超過料箱容積，同類貨品可存儲在多個料箱中。對待揀選列表中的任一貨品，搜索所有存儲該貨品的料箱并確認庫存，當需求量小于某個料箱現有庫存量時，調用該目標箱；當需求量大于料箱最大庫存量時，需將該貨品訂單拆分成兩個訂單甚至更多，直到每個子訂單的需求能被單個料箱滿足。對訂單進行拆分能將訂單任務與需要提取的料箱一一對應，確定目標箱集合N={1,2,…,n},n≥初始訂單數。

目標箱確定后，其所在三維坐標系的位置也可以確定，則對應阻礙箱也可以確定。對于目標箱i∈N,存在阻礙箱集合Ei={1,2,…,ni},ni為目標料箱i上面阻礙箱的數目。同批次訂單內，所有阻礙箱集合為E={E1,E2,…,En},共有m個阻礙箱，m=n1+n2+…+ni,i∈N。

倒箱操作需將目標箱上的阻礙箱依次轉移到其他貨格的空余箱位。如圖1所示，若c(1,1,2)為目標箱，則b(1,1,3)和a(1,1,4)為阻礙箱，需依次搬運至其他空位。確定每個阻礙箱的落箱位是倒箱操作的核心環節，落箱位需滿足當前時刻為空箱且下方為實箱位的條件，如圖1中， g被占用，e下方為空，均不滿足條件，f、i可作為落箱位。對于阻礙箱j∈E,設落箱位置集合為Dj={1,2,…,mj},其中mj為阻礙箱j的可落箱位置數目。對于所有阻礙箱，落箱位置集合為D={D1,D2,…,Dm}。

通過以上分析，AGV路徑規劃問題可轉化為：將訂單分解形成目標箱集合N,調用多個AGV,將阻礙箱集合E中的料箱搬運至集合D,將目標箱集合N中的料箱搬運至工作臺W接受服務并返回，在滿足相關約束的前提下，獲得AGV行駛路徑，以提高系統運行效率。

分析可知，AGV任務可分解成兩類子任務：搬運阻礙箱和搬運目標箱。對搬運阻礙箱子任務，落箱位不確定，且當某一目標箱上面存在多個阻礙箱時，AGV需要多次返回倒箱；當多個AGV同時進行倒箱操作時，落箱位很容易出現沖突，因此，該任務求解的核心在于建立一個動態箱位狀態數據庫。對搬運目標箱子任務，需要AGV通過最短路徑將目標箱搬運至工作臺，問題的核心為多AGV任務指派。這兩個任務既有一定獨立性又有一定的順序約束，根據AGV調用情況， 有兩種策略可以選擇：一是將目標箱和其對應阻礙箱安排給同一AGV,即AGV接收到任務后，行走到目標箱頂層，先進行倒箱，再搬運目標箱；二是將AGV分成兩部分，一部分只負責倒箱，一部分只負責搬運?？紤]到目標箱和相應阻礙箱都在同一貨格，采用第二種方法容易產生沖突，因此，使用第一種策略。

為此，將AGV路徑規劃抽象成一個車輛路徑問題(vehicle routing problem, VRP):給多個任務(包含倒箱和搬運目標箱)安排AGV,每個任務必須且只能被完成一次。AGV完成任務的時間分解成4部分：①從當前位置移動到目標箱頂層的空駛時間，由AGV路徑規劃確定；②倒箱時間，由阻礙箱數目及各自落箱位確定；③目標箱直提時間，由目標箱縱向坐標確定；④水平搬運至工作臺時間，由AGV路徑規劃確定。

基于以上假設，可建立AGV路徑規劃雙層優化模型，內層模型求解指定任務的倒箱時間，以此為基礎，利用外層模型對多AGV路徑規劃問題進行分析。

倒箱路徑優化問題可以轉化成單AGV路徑規劃問題：調用AGV依次搬運阻礙箱，需確定落箱位，優化目標為完成時間最短。且為了與外層路徑規劃模型相匹配，在內層模型中，AGV初始位置和終點位置均為目標箱貨格頂層。

對于任一阻礙箱i∈E,其落箱位包含兩方面的信息：一是水平坐標，表示AGV要搬運至何處；二是縱向坐標，表示放入位置的深度。在求解落箱位前，先確定倒箱規則。

規則1 落箱位選擇范圍確定。為避免阻礙箱落在訂單內其他目標箱上造成重復倒箱，需先行確定落箱位水平坐標范圍。

設目標箱水平坐標為(x0,y0),除此之外所有貨格平面坐標集合為GSW。但在GSW中，并不是每個貨格都能作為落箱位使用，得排除掉以下兩種情況：

①已存滿料箱的貨格，設貨架中滿載的貨格水平坐標集合為FS。②同批次訂單內其他目標箱所在貨格，設目標箱所在貨格水平集合為NS。以上兩個集合可以通過判斷貨架存儲狀態確定。設可儲存平面坐標集合為ASW,則有ASW=GSW-(GSW∩FS)-(GSW∩NS)。

規則2 落箱位滿足堆放約束。阻礙箱的落箱位必須為空，且當落箱位置不在第一層時，其下方相鄰箱位不為空。對箱位集合M中的箱位si,坐標為si(xi,yi,zi)。用θ(si)表示位置si的當前狀態，若有箱，則θ(si)=1,否則=0。

對阻礙箱j,設落箱位集合為Dj,結合規則1,則有Dj={si|θ[si(xi,yi,zi)]=0,(xi,yi)∈ASW,zi=1或θ[s(xi,yi,zi)]=0,θ[si(xi,yi,zi-1)]=1, (xi,yi)∈ASW,zi≥2,si∈M。

根據1.2節所述集合，任取目標箱i∈N(N為所有目標箱集合),其箱位坐標為(xi,yi,zi),相應阻礙箱集合為Ei;任取j∈Ei,有落箱位集合Dj,滿足式(1);對k∈Dj,設(Xk,Yk,Zk)為決策變量；為使得阻礙箱j的倒箱時間SDj最小，建立最小化AGV水平行駛和提升時間之和的優化目標，可表示為

SDj=min{(|Xk-xi|+|Yk-yi|)th+|Zk-zi|tv}, ?k∈Dj(1)

式(1)中： th、tv分別為AGV水平行駛單位距離時間和垂直提升單位距離時間。

對i∈N,其上部所有阻礙箱倒箱時間Sdi,可表示為

Sdi=∑j∈EiSDj,??i∈NSid=∑j∈EiSjD,??i∈Ν (2)

外層模型以內層模型為基礎，并滿足以下假設：①考慮單一工作臺；②初始倉庫堆存狀態已知，不考慮缺貨無法滿足訂單需求的情況；③所有AGV勻速行駛，且不考慮重量影響；④對某一目標箱，阻礙箱倒箱和目標箱提取由同一個AGV完成，每AGV每次最多搬運一個料箱。

設N={1,2,…,n}為所有目標箱集合；設虛擬任務點集合A={0,1,2,…,n},0表示AGV初始化位置；K={1,2,…,m}為所有AGV集合；工作臺坐標為(Work_X0, Work_Y0, Work_Z0)。

對目標箱i∈N,Si為目標箱i所需服務的總時間，由以下3部分組成：倒箱時間Sdi;從存儲箱位提升到貨架頂層的時間Sti;從貨架頂層移動到工作臺所需時間Sgi。

對小車k∈K,(AGV_Xk,AGV_Yk,AGV_Zk)為初始位置坐標，Tkijijk為AGV從目標箱i貨格頂層移動到目標箱j貨格頂層所需時間。

決策變量可表示為Xkijijk∈{0,1},?k∈K,?i∈A,?j∈A時，表示小車k與目標箱的服務關系，若小車k服務完目標箱i后服務目標箱j,取值為1,否則為0;Zkiik∈{0,1},?k∈K,?i∈A,表示小車k與目標箱i的服務關系，若目標箱i被小車k運送，取值1,否則為0。

為保證出庫作業快速完成，以最小化AGV最長作業時間為目標，包括前往目標箱的空駛時間與服務于目標箱的工作時間，目標函數的表達式為

與目標箱服務時間相關約束為

Si=Sdi+Sti+Sgi, ?i∈N(4)

Sti=|(zmax+1)-zi|tv, ?i∈N(5)

Sgi=(|xi-Work_X0|+|yi-Work_Y0|)th,?i∈N(6)

式(5)為目標箱i所需服務時間Si計算方法，其中Sdi、Sti、Sgi求解分別如式(2)、式(5)、式(6)。

與AGV任務指派相關約束為

∑k∈K∑j∈A,j≠iXkij=1,??i∈N∑k∈Κ∑j∈A,j≠iXijk=1,??i∈Ν (7)

∑k∈K∑i∈A,i≠jXkij=1,??j∈N∑k∈Κ∑i∈A,i≠jXijk=1,??j∈Ν (8)

Zki=∑j∈A,j≠iXkji,??k∈KΖik=∑j∈A,j≠iXjik,??k∈Κ; ?i∈A(9)

式(7)、式(8)表示每個目標箱都會被訪問唯一一次，式(9)表示若小車k從目標箱j到目標箱i,則目標箱i被小車k服務。

與AGV空駛相關約束為

Tkijijk=(|xi-xj|+|yi-yj|)th, ?k∈K;?i∈N,?j∈N(10)

Tk0j0jk=(|AGV_Xk-xj|+|AGV_Yk-yj|)th,?k∈K,?j∈N(11)

Tki0i0k=(|xj-AGV_Xk+|yj-AGV_Yk|)th,?k∈K,?i∈N (12)

∑j∈NXk0j=1,??k∈K∑j∈ΝX0jk=1,??k∈Κ (13)

∑j∈NXkj0=1,??k∈K∑j∈ΝXj0k=1,??k∈Κ (14)

式中：Tkijijk為小車從目標箱i頂層移動到目標箱j頂層需要的時間，等于貨架之間的折線距離乘以小車行駛單位距離時間；Tk0j0jk為小車從初始?？奎c到目標箱j頂層所需的時間；Tki0i0k為小車從目標箱i頂層返回初始?？奎c所需的時間；Xkojojk、Xkj0j0k分別為小車從初始?？奎c出發、最終返回初始?？奎c。

根據魔方型倉儲結構及優化模型的特點，算法需解決以下5個核心問題。

通過三維柵格法建成貨架結構后，可根據實際情況依次設定存有料箱的箱位。但為了提高算法適用性，能多次重復進行不同規模的試驗，建立倉儲狀態隨機生成子系統，主要步驟為：①確定需生成的存儲比例；②在所有空余箱位中，隨機生成一個料箱；③判斷該料箱是否滿足堆存規則，即除了在第一層，下層不能為空，滿足則留下該料箱，否則刪除；④重復②,直到料箱數量/總箱位數達到要求的存儲比例。

倒箱和移箱不僅會使得相應箱位狀態發生變化，更會影響隨后的決策。建立一個箱位狀態數據庫，在提取和存入等關鍵節點及時更新。路徑尋優過程中，均在當前箱位狀態下進行。

多AGV同時作業屬于多線程并行問題。在已有多AGV路徑規劃研究中，該問題的求解一般分為兩步：首先不考慮時間線，將多AGV依次分配給多個任務，得到數條初始規劃路徑；其次，考慮每段路徑的起止時間約束，將所有路徑安排在同一時間軸上，得到可執行路徑。在所研究的AGV路徑規劃問題，除了將目標箱搬運至工作臺外，還需要接受入庫指令，入庫指令的時間取決于工作臺的服務狀態，無法通過計算式直接求解。因此，采用仿真模擬的思想，在路徑規劃時就引入時間線，建立AGV實時并行系統，一步生成路徑方案。

多AGV多任務指派的核心在于確定目標箱提取順序和AGV調用策略?？紤]到同波次訂單已經在目標箱生成中被打亂順序，按到達時間順序提取意義不大。在魔方型倉儲中，壓箱會造成過多的倒箱，因此，設定提取原則為：目標箱提取順序與其阻礙箱數目成反比，當阻礙箱數目一致時，越靠近貨架底層的越先提取，以減少后期被壓箱的可能性。

確定目標箱提取順序后，依次將任務安排給AGV。AGV安排策略有兩種，先完成先分配和輪流分配。先完成先分配能減少在貨格頂層移動的AGV數目，減少沖突，因此采用此策略。

將某個目標箱任務指派給某AGV后，該AGV的路徑生成可以分解成3個階段：①從接收到指令時的當前位置移動到目標箱頂層，用最短折線路線法生成行駛路徑；②倒箱路徑生成，首先根據倒箱路徑優化模型求得最優落箱位，其次采用最短折線路線法生成倒箱路徑；③將目標箱提升到頂層后，通過最短折線路線法生成到工作臺的路徑。

采用Python語言編寫算法程序。算法從結構上可以分為內外兩層，兩層互相嵌套互相影響。外層求解多AGV指派多個任務問題，需要建立兩個列表，待執行任務列表和空閑AGV列表，從任務列表中依次提取目標箱，將其分配給AGV列表中的小車，過程中需滿足上節所述任務安排及AGV調用策略。外層主要結構如圖2所示。

外層結構中的單AGV路徑規劃方案需調用內層算法求解。內層算法的已知條件為將小車I配置給了目標箱i,目標箱位置為(x,y,z),包括4個步驟：①確定阻礙箱列表；②確定有效空位列表；③依次將所有阻礙箱搬運至最優空位；④搬運小車至工作臺。內層算法結構圖如圖3所示。

AutoStore系統中，倉儲規模、存儲率、AGV數目、目標箱數目4個參數會直接影響AGV路徑尋優的結果。先通過一典型工況對算法的有效性進行分析；再對不同參數取值進行對比，以分析算法的效率及適應性。

設典型工況基本參數為：倉庫規模為10×10×10;倉儲率為75%;AGV數目為5臺；隨機生成20個目標箱位；同時AGV水平行駛速度為3格/s, 垂直提升速度為2格/s。算法隨機生成的倉儲系統如圖4所示。

通過嵌套式啟發式算法進行求解，可得到每個AGV的任務分配方案及行走路徑。首先以2號AGV為例，進行路徑分析。圖5中，目標箱位置為(10,2,8),上面有一個障礙箱(10,2,9),小車的當前位置在(4,1,11)。小車的路徑一共分為以下5步：①從當前位置水平移至目標箱貨格頂層(10,2,11);②伸縮臂伸入貨格提取障礙箱至頂層；③通過倒箱路徑尋優模型，找到最近的倒箱位置(8,2,10),將障礙箱放入；④返回至目標箱頂層；⑤將目標箱搬運至工作臺(10,10,11)。

所有AGV路徑方案統計如表1所示。AGV遵循輪流分配策略，每臺車服務的目標箱數目均為4臺，總服務時間差別不大。倒箱服務存在大量的往返操作，因此，各AGV空載和負載時間也相差不大。對此工況，算法求解效率較高，僅為0.12 s。

AutoStore系統一般布置在室內，考慮到空間高度，一般層數為10～20層。為使研究更為普遍性，倉儲規模為10×10×10、15×15×15、20×20×20,倉儲率為75%,5臺AGV,20個目標箱工況下，統計AGV作業時間和運算效率，如表2所示。倉儲規模增大后，目標箱分散度增加，單AGV和所有AGV作業時間大幅度增加。運算時間也大幅度增加，但絕對值不高。

對4.1節工況增加AGV數，即倉儲規模10×10×10,存儲率75%,20個目標箱對應計算結果如表3所示。AGV數量翻倍后，單個AGV分配的目標箱只有原來的1/2,因此作業時間也相應減少。相應的，等待AGV的時間也有所減少，使得總作業時間減少。求解效率影響不大。

倉儲率會影響倒箱位置和垂直提升距離，在倉儲規模為15×15×15,5臺AGV,20個目標箱，倉儲率分別為50%,75%,90%工況下計算結果如表4所示。當倉儲率發生變化時，受目標箱位置隨機分布的影響，最長AGV作業時間變化不明顯?？傋鳂I時間隨著倉儲率增加而增加，通過分析具體路徑發現，當倉儲率高時，阻礙箱數目增加，倒箱次數增多。運算效率隨倉儲率提高而提高，主要是因為當倉儲率較高時，落箱位的選擇性變少，更容易找到倒箱位置。

在倉儲規模為20×20×20,倉儲率為75%,5臺AGV的工況下，計算對比結果如表5所示。隨著目標箱增多，單個AGV服務時間增加，總時間增加，呈較明顯的正相關關系?？紤]到目標箱生成的隨機性，運算效率變化規律在此不明顯，但絕對值都不高。 表5 目標箱變化下AGV方案及求解效率對比

(1)AGV雙層路徑規劃模型能將倒箱路徑尋優與多AGV任務分配及尋優進行結合，符合AutoStore系統的工作特性，算例中的AGV路徑方案也證明了在三維空間探索的有效性。

(2)根據模型特點給出了嵌套式啟發式算法，通過Python編寫算法程序，重點解決了倉儲狀態隨機生成子系統、箱位狀態數據庫系統、多AGV并行系統、AGV任務分配系統及路徑生成系統等核心問題。

(3)不同工況的算例結果表明：倉儲規模增大后，目標箱分散度增加，AGV作業時間大幅度增加；AGV數量和作業時間負相關；倉儲率提高會增加倒箱幾率，增加作業時間；目標箱數目變化與AGV作業時間正相關。在求解效率方面，主要受目標箱隨機生成位置和倉儲率影響，但絕對值也僅在10秒左右。

(4)需說明的是，僅研究了將目標箱移動至工作臺這一階段，在下一步工作中，會與目標箱返回相結合。同時因貨格頂層行走路徑較多，未特意設置沖突解決策略。在實際求解中，當兩車需同時占用一個節點時，隨機選取其一為優先級高的車，讓其先行，另外一輛車等待即可。