[發明專利]基于時間和位置的遞送最優化

有效

• 申請號: 201310532551.8
• 申請日: 2013-10-31
• 公開（公告）號: CN104598979B
• 公開（公告）日: 2021-10-08
• 發明（設計）人: R.王;王夢蛟;黎文憲
• 申請（專利權）人: SAP歐洲公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/28
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 錢大勇

1.一種用于管理包裹遞送的計算機化的方法，所述方法包括：

建立表示總部并且包括相應遞送車輛的容量的、樹中的根節點；

將指數設置為初始值，所述指數表示樹的等級；

如果到一個或多個未分配的遞送點的路徑是可行的，則將相應的未分配的遞送點添加作為根節點的子節點；

將指數設置為初始值加1；

如果下一等級遞送點是未分配的，并且到該下一等級的遞送點的路徑是可行的，則將該下一等級的遞送點添加作為在樹的等級指數中的節點的子節點，對于未分配的遞送點和在樹的等級指數中的節點的每一個組合重復所述添加步驟；

增加指數；以及

重復添加下一等級的遞送點和所述增加步驟，直到指數大于遞送點的計數，

其中，未訪問的遞送點m具有到達時間窗口[LS_n+T_nm，LE_n+T_nm]，以及可行的到達時間窗口

[AS_m，AE_m]＝[LS_n+T_nm，LE_n+T_nm]∩[TS_m-TW，TE_m]，

其中，LS_n是用于樹中的節點n的可行時間窗口的開始；

LE_n是用于樹中的節點n的可行時間窗口的結束；

T_nm是從點n到點m的行駛時間；

TS_m是對于需求點d要求的時間窗口的開始；

TE_m是對于需求點d要求的時間窗口的結束；

AS_m是用于樹中的節點n的可行的到達時間窗口的開始；

AE_m是用于樹中的節點n的可行的到達時間窗口的結束；以及

TW是在需求點處的最大等待時間。

2.根據權利要求1所述的方法，其中，如果

并且Wm≤Cn，則遞送點是可行的，

其中，W_m是用于需求點m的遞送的重量；以及

C是卡車的容量。

3.根據權利要求1所述的方法，其中，可行的離開時間窗口是

[LS_m，LE_m]＝[max(AS_m,TS_m)+TU_m，max(AE_m,TS_m)+TU_m]

其中，LS_m是用于在樹中的節點m的可行時間窗口的開始；

LE_m是用于樹中的節點m的可行時間窗口的結束；以及

TU_m是用于需求點m的卸載時間。

4.根據權利要求1所述的方法，進一步包括剪除包括少于節點閾值的計數的節點的路徑。

5.根據權利要求1所述的方法，進一步包括剪除其中在路線上的遞送的總重量低于重量閾值的路徑。

6.根據權利要求1所述的方法，進一步包括剪除重復的路徑集合中的、其完成時間晚于重復的集合中的另一路徑的路徑。

7.根據權利要求1所述的方法，進一步包括剪除重復的路徑集合中的、其行駛距離長于重復的集合中的另一路徑的路徑。

8.根據權利要求1所述的方法，其中，路線的利潤是o＝r-s*G-t*P

其中，o是利潤；

r是路線的總的遞送收入；

s是在路線上的連續節點之間的行駛距離與從葉節點到總部的直接距離的總和；

G是卡車行駛單位距離的成本；

t是總的行駛時間；以及

P是卡車司機每單位時間在總部外部的成本。