[發明專利]一種零散快遞合作攬件方法

在審

• 申請號: 202110104048.7
• 申請日: 2021-01-26
• 公開（公告）號: CN113159370A
• 公開（公告）日: 2021-07-23
• 發明（設計）人: 孫鵬飛;徐佳;蔣凌云;駱健;徐力杰;周遠航;魯蔚鋒;高興
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 曹坤

1.一種零散快遞合作攬件方法，其特征在于，具體步驟如下：

步驟(1.1)、用戶提交快遞包裹信息到合作攬件分配系統；

步驟(1.2)、通過接收到的快遞包裹信息確定包裹分配方案；

所述的包裹分配方案具體包括：建立小件攬件合作模型和大件攬件合作模型、形式化快遞包裹合作分配問題、轉化快遞包裹合作分配問題及采用快遞包裹合作分配算法得到聯盟結構；

步驟(1.3)、根據確定的包裹分配方案，采用最近鄰居算法為每一個聯盟確定快遞員攬件路徑；

步驟(1.4)、采用成本分攤機制確定用戶的實際支付額。

2.根據權利要求1所述的一種零散快遞合作攬件方法，其特征在于，

在步驟(1.1)中，所述用戶提交快遞包裹信息到合作攬件分配系統中，

設快遞站集合M＝{1,2,L,m}，

其中，m表示快遞站的數量，設每個快遞站j∈M的位置用l^j來表示，每一個快遞站有且僅有一個快遞員進行攬件服務；

用戶的集合為N＝{1,2,L,n}，

其中，n表示用戶的數量，每個用戶i∈N提交各自的快遞包裹信息B_i＝(l_i,w_i)到服務器，

其中，l_i,w_i表示用戶i的當前位置以及用戶快遞包裹的重量。

3.根據權利要求1所述的一種零散快遞合作攬件方法，其特征在于，在步驟(1.2)中，所述確定包裹分配方案的具體操作步驟如下：

(1.2.1)、建立小件攬件合作模型和大件攬件合作模型：

所述的小件攬件合作模型指所有用戶快遞包裹重量均小于首重重量，形成聯盟后的聯盟中的用戶的快遞包裹總重量均小于或等于首重重量；

所述的大件攬件合作模型指用戶快遞包裹重量均大于首重重量；

具體的，設分配到同一個快遞站j的用戶集合為聯盟，用G_j表示，設聯盟G_j的快遞費為φ(G_j)，聯盟G_j的綜合成本為c^*(G_j)；

在小件攬件合作模型中，規定聯盟G_j的快遞費φ(G_j)可如下計算得到：

φ(G_j)＝p^f(1)

式(1)中，p^f表示首重重量；

在大件攬件合作模型中，聯盟G_j的快遞費φ(G_j)可如下計算得到：

式(2)中，w_i表示用戶快遞包裹的重量，p^f和p^c分別表示寄件首重價格和續重價格，H^f表示首重重量；

聯盟G_j的綜合成本c^*(G_j)可計算為：

式(3)中，χ表示快遞員的單位移動成本，表示快遞員j從l^j出發攬收聯盟G_j中所有用戶的包裹，并回到l^j的移動距離；

規定快遞計費規則滿足下述規則：

p^f≥p^cH^f； (4)

(1.2.2)、形式化快遞包裹合作分配問題；

合作攬件分配系統中所有用戶被分配且只能被分配到一個快遞站進行攬件，

建立約束以保證所有用戶被完全分配，

建立約束以保證所有用戶只能被分配到一個快遞站；

優化目標是最小化所有聯盟的總綜合成本，形式化快遞包裹合作分配問題：

(1.2.3)、轉化快遞包裹合作分配問題：

將快遞包裹合作分配問題的目標轉化為如下問題

s.t.公式(6)和公式(7)

(1.2.4)、采用快遞包裹合作分配算法得到聯盟結構；

定義聯盟結構G＝(G₁,G₂,...,G_m)為所有聯盟的集合，對于小件攬件合作模型和大件攬件合作模型下的快遞包裹合作分配問題，分別采用快遞包裹合作分配算法得到聯盟結構；其具體操作步驟如下：

(1)、為每一個快遞站j∈M初始化一個空的聯盟初始化未分配的用戶候選集合N'，使得N'＝N；

(2)、對于每一個快遞站j∈M，在N'中通過二分搜索找到聯盟G_j的綜合成本與新加入用戶數量比值最小的用戶集合S_j；

(3)、在所有快遞站中找到聯盟綜合成本與新增用戶數量比值最小的那個快遞站j，即

(4)、將S_j中用戶合并到快遞站j的聯盟中，即G_j←G_jUS_j；

(5)、將S_j從未分配的用戶候選集合N'中移除，即N′←N′\S_j；

(6)、重復執行步驟(2)到步驟(5)，直到未分配的用戶候選集合N'為空；

(7)、返回聯盟結構G。