计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
3期
218-222
,共5页
车辆路径问题%时间窗%时空距离%聚类分析%遗传算法%可变邻域搜索
車輛路徑問題%時間窗%時空距離%聚類分析%遺傳算法%可變鄰域搜索
차량로경문제%시간창%시공거리%취류분석%유전산법%가변린역수색
Vehicle routing problem%Time windows%Spatiotemporal distance%Clustering analysis%Genetic algorithm%Variable neighborhood search
针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法.首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解.以含1000个点的标准问题集作为算例,计算结果表明,与不采用时空聚类的方法相比,该算法能在更短的时间内取得更好的解,显示了在解决大规模车辆路径问题时具有很好的潜力.
針對帶時間窗車輛路徑問題,設計瞭一種同時攷慮顧客的時間和空間鄰近性的路徑改進方法.首先設計瞭一種顧客間時空距離的錶達方式,然後利用遺傳算法對顧客點進行時空聚類,併將聚類結果應用于路徑調整中,使得顧客儘可能被加入到時空距離近的顧客所在路徑中,這樣既能有效減小搜索範圍,又能更快到達更好的解.以含1000箇點的標準問題集作為算例,計算結果錶明,與不採用時空聚類的方法相比,該算法能在更短的時間內取得更好的解,顯示瞭在解決大規模車輛路徑問題時具有很好的潛力.
침대대시간창차량로경문제,설계료일충동시고필고객적시간화공간린근성적로경개진방법.수선설계료일충고객간시공거리적표체방식,연후이용유전산법대고객점진행시공취류,병장취류결과응용우로경조정중,사득고객진가능피가입도시공거리근적고객소재로경중,저양기능유효감소수색범위,우능경쾌도체경호적해.이함1000개점적표준문제집작위산례,계산결과표명,여불채용시공취류적방법상비,해산법능재경단적시간내취득경호적해,현시료재해결대규모차량로경문제시구유흔호적잠력.
