系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2011年
10期
1912~1920
,共null页
张涛 余绰娅 刘岚 邵志芳 张玥杰
張濤 餘綽婭 劉嵐 邵誌芳 張玥傑
장도 여작아 류람 소지방 장모걸
随机旅行时间车辆路径问题 同时送取货车辆路径问题 混合整数规划 分散搜索算法
隨機旅行時間車輛路徑問題 同時送取貨車輛路徑問題 混閤整數規劃 分散搜索算法
수궤여행시간차량로경문제 동시송취화차량로경문제 혼합정수규화 분산수색산법
vehicle routing with stochastic traveling time; vehicle routing with simultaneous pick-up and delivery; mixed integer programming; scatter search
建立了同时送取货的随机旅行时间车辆路径问题(STT-VRPSPD)的机会约束规划模型,构建了分散搜索算法求解策略.分散搜索算法中,针对STT-VRPSPD问题的复杂特性,构造了解的改进策略、组合策略,并采用改进的节约算法构造分散搜索算法初始解,从而使文中设计的分散搜索算法更加适应STT-VRPSPD问题特有的负载波动性.仿真实验中,首先对分散搜索算法的参数设置进行分析,确定了最优参数组合;然后基于经典的Dethloff算例数据,构造了STT-VRPSPD的测试算例,并对分散搜索算法和遗传算法进行了对比分析,结果表明,分散搜索算法对于STT-VRPSPD的求解质量优于遗传算法.
建立瞭同時送取貨的隨機旅行時間車輛路徑問題(STT-VRPSPD)的機會約束規劃模型,構建瞭分散搜索算法求解策略.分散搜索算法中,針對STT-VRPSPD問題的複雜特性,構造瞭解的改進策略、組閤策略,併採用改進的節約算法構造分散搜索算法初始解,從而使文中設計的分散搜索算法更加適應STT-VRPSPD問題特有的負載波動性.倣真實驗中,首先對分散搜索算法的參數設置進行分析,確定瞭最優參數組閤;然後基于經典的Dethloff算例數據,構造瞭STT-VRPSPD的測試算例,併對分散搜索算法和遺傳算法進行瞭對比分析,結果錶明,分散搜索算法對于STT-VRPSPD的求解質量優于遺傳算法.
건립료동시송취화적수궤여행시간차량로경문제(STT-VRPSPD)적궤회약속규화모형,구건료분산수색산법구해책략.분산수색산법중,침대STT-VRPSPD문제적복잡특성,구조료해적개진책략、조합책략,병채용개진적절약산법구조분산수색산법초시해,종이사문중설계적분산수색산법경가괄응STT-VRPSPD문제특유적부재파동성.방진실험중,수선대분산수색산법적삼수설치진행분석,학정료최우삼수조합;연후기우경전적Dethloff산례수거,구조료STT-VRPSPD적측시산례,병대분산수색산법화유전산법진행료대비분석,결과표명,분산수색산법대우STT-VRPSPD적구해질량우우유전산법.
This paper set up a chance-constrained programming model for STT-VRPSDP(stochastic traveling time vehicle routing problem with simultaneous pick-up and delivery),designed respectively a scatter search algorithm applicable to this problem.In response to the complexity of STT-VRPSDP, this paper constructed innovatively an improvement method and a combination method derived from the basic theory of scatter search algorithm.Moreover,with C-W algorithm as an approach to get the initial solution to scatter search algorithm,the scatter search algorithm designed in this paper catered better to the loading floating feature particular to STT-VRPSDP and therefore could better the quality of solution. The simulation experiment firstly analyzed the parameters setting of scatter search algorithm,after which several sets of instances were chosen for the purpose of comparing and analyzing scatter search algorithm and genetic algorithm.The computation results show that solutions of scatter search algorithm are better than those of genetic algorithm.