求解軟硬時間窗共存配送路徑問題的改進遺傳算法

史 昊，何俊生，馬 暢

(重慶交通大學交通運輸學院，重慶 400074)

現實中的配送客戶往往會提出期望的收貨時間區(qū)間，要求配送車輛在這期間到達。按對送達時間要求的嚴格程度不同，時間窗分為軟時間窗和硬時間窗。近年來，有關軟時間窗或帶硬時間窗的軟時間窗車輛路徑問題的研究較多[1]，但對節(jié)點時間窗軟硬不同且同時存在的情況的車輛路徑問題的研究還比較少，而這種情況在現實的配送問題中時常出現。本文給出一種改進的遺傳算法，對軟硬時間窗共存配送路徑問題進行求解，并與基本的遺傳算法計算效果進行對比。

1 模型

1.1 問題描述

車輛從某固定的配送中心出發(fā)，給已知的配送服務節(jié)點進行配送。每個節(jié)點都要求一個已知固定配送服務時間窗。假設每個客戶節(jié)點只由一輛車進行服務，且足以滿足該節(jié)點對進貨量的需求。所有節(jié)點(包括配送中心和客戶節(jié)點)間距、每個配送點的需求量和服務時間、車輛的載重量及最大允許的行駛距離都為已知。在車輛配送過程中還要受到以下基本約束〔2-3〕：①車輛不允許超載；②車輛有最大行程限制；③時間窗限制。

本文研究在所有約束條件都滿足的情況下，如何確定配送的路線方案，使目標成本最小。

1.2 建模

根據上述對問題的描述，做如下假設〔4-6〕：設配送中心共有n個服務節(jié)點，i,j表示節(jié)點的編號(i,j=1,2,3,…，n)，配送中心編號為0；每個節(jié)點的需求量為Pi，單車的最大裝載量為p； 節(jié)點之間的距離dij，節(jié)點的服務時間為Ti；……