[發明專利]一種煙草物流配送路徑規劃方法

在審

• 申請號: 201310310752.3
• 申請日: 2013-07-22
• 公開（公告）號: CN103383756A
• 公開（公告）日: 2013-11-06
• 發明（設計）人: 楊金欣;王森芳;徐源奇
• 申請（專利權）人: 浙江省煙草公司紹興市公司
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q50/28
• 代理公司: 紹興市越興專利事務所 33220
• 代理人: 蔣衛東

1.一種煙草物流配送路徑規劃方法，其特征在于包括如下步驟：

1）對該地區內的所有零售戶進行聚類步驟；

2）基于離散模型的站點與服務區規劃步驟；

3）基于配送工作量模型的最優路徑確定步驟；

4）訂單日規劃步驟。

2.如權利要求1所述的一種煙草物流配送路徑規劃方法，其特征在于：上述步驟1）采用的聚類算法包括自下而上的一階段方法和直接指派的方法，其中

自下而上的一階段方法包括：

初始步驟：初始狀態：每個零售點都是一個類；

中間步驟：如果類的容量還沒有達到上限，臨近的類相互聚合；

終止條件：沒有類可以再聚合；

在利用自下而上的一階段方法獲得初始聚類結果后，再將這一結果中，符合設定要求的前若干個類作為直接指派方法的初始核，應用直接指派的方法進行計算，直接指派的方法包括：

初始狀態：指定類的數目，并指定每個類的初始核；

中間步驟：如果類的容量還沒有達到上限，將每個零售點向最接近的類聚合；更新類的核；

終止條件：所有點都已聚合到相應的類。

3.如權利要求1所述的一種煙草物流配送路徑規劃方法，其特征在于：上述步驟2）站點與服務區規劃包括：

（1）、將整個配送地區均分為（30～50）*（30～50）的點陣，總共900～2500個候選點，相鄰候選點東西間距3～5公里，南北間距3～5公里；

（2）、給定站點數目，以最小化總里程為目標，采用數學模型計算最佳的選址方案，具體為：給定p個中轉站，求解最佳站點位置和服務區規劃的數學模型如下所示：

minΣixi1di1+ΣiΣj=2nxijdij+Σj=2ny1jd1j---(0.1)]]>

Σjyj=p---(0.2)]]>

xij≤yj,∀j=2,3,...,n---(0.3)]]>

Σjxij=1,∀i---(0.4)]]>

Σixij/n*c=y1j,∀j---(0.5)]]>

其中，y_j是確定站點位置的決策變量，如果候選站點j被選為站點，則y_j=1，否則y_j=0；x_ij是確定服務區規劃的決策變量，如果零售點聚類i由候選站點j服務，則x_ij=1；否則x_ij=0；

公式（0.1）則是目標函數，其中d_i1表示的是從零售點聚類i到總配送中心的距離；是所有由總配送中心配送的零售點聚類到總配送中心的距離之和，則是由中轉站配送的零售點聚類到中轉站的距離之和，則是從總配送中心到中轉站中轉運輸的距離之和；

公式（0.2）則表明，有且只有p個中轉站可供選擇；

公式（0.3）則表明，只有當候選點j被選作中轉站的時候，才能配送零售點；

公式（0.4）則表明，每個零售點聚類由且只能由一個中轉站配送；

公式（0.5）則是將中轉運輸的距離折算為配送運輸的距離，其中n表示每輛中轉車輛可以服務的配送車輛數目，則表示候選站點j需要的中轉車輛數目，而c表明中轉車輛行駛一公里相當于配送車輛行駛c公里。

在求解過程中，模型中有關的參數如下：

d_ij：即各個零售點聚類到配送中心、各個零售點聚類到候選站點的距離由GIS系統實測獲得；

c和n：即配送車輛和中轉車輛的轉換系數，根據省煙草的統一規劃和地方煙草公司的實際情況，在規劃中一般c=1～5，n=4～9；

分別計算當p=0～6時，配送總里程的公里數；

（3）、通過聚類計算和確定的站點數，確定最優的總配送中心和站點的經度和緯度，比較不同站點數目的選址方案，結合配送成本、車輛的冗余性等綜合管理成本，選擇最優選址方案。