计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
7期
248-253
,共6页
党兰学%王震%刘青松%孔云峰
黨蘭學%王震%劉青鬆%孔雲峰
당란학%왕진%류청송%공운봉
校车路径问题%混载%有时间窗装卸问题%记录更新法
校車路徑問題%混載%有時間窗裝卸問題%記錄更新法
교차로경문제%혼재%유시간창장사문제%기록경신법
School bus routing problem (SBRP)%Mixed load%Pickup and delivery with time window (PDPTW)%Record-to-record travel (RRT)
对一个区域内多所学校进行校车路径规划时,允许校车混载不同学校的学生能显著地减少校车数量,从而降低运营成本.已有学者针对允许混载的校车路径问题(SBRP)提出了启发式算法,但这些算法对邻域解的搜索不够全面,在缩减路径方面仍有较大的提升空间.提出了一种以记录更新法(record-to-record travel,RRT)为基础的启发式算法.该算法从初始解出发,利用求解有时间窗装卸问题(PDPTW)时使用的算子搜索邻域解,逐步优化校车路径数目.与现有算法相比,该算法扩展了求解混载SBRP的启发策略,能够在全局范围内对校车路径进行优化,从而获得所需校车较少的路径规划方案.实验结果验证了该算法的有效性.
對一箇區域內多所學校進行校車路徑規劃時,允許校車混載不同學校的學生能顯著地減少校車數量,從而降低運營成本.已有學者針對允許混載的校車路徑問題(SBRP)提齣瞭啟髮式算法,但這些算法對鄰域解的搜索不夠全麵,在縮減路徑方麵仍有較大的提升空間.提齣瞭一種以記錄更新法(record-to-record travel,RRT)為基礎的啟髮式算法.該算法從初始解齣髮,利用求解有時間窗裝卸問題(PDPTW)時使用的算子搜索鄰域解,逐步優化校車路徑數目.與現有算法相比,該算法擴展瞭求解混載SBRP的啟髮策略,能夠在全跼範圍內對校車路徑進行優化,從而穫得所需校車較少的路徑規劃方案.實驗結果驗證瞭該算法的有效性.
대일개구역내다소학교진행교차로경규화시,윤허교차혼재불동학교적학생능현저지감소교차수량,종이강저운영성본.이유학자침대윤허혼재적교차로경문제(SBRP)제출료계발식산법,단저사산법대린역해적수색불구전면,재축감로경방면잉유교대적제승공간.제출료일충이기록경신법(record-to-record travel,RRT)위기출적계발식산법.해산법종초시해출발,이용구해유시간창장사문제(PDPTW)시사용적산자수색린역해,축보우화교차로경수목.여현유산법상비,해산법확전료구해혼재SBRP적계발책략,능구재전국범위내대교차로경진행우화,종이획득소수교차교소적로경규화방안.실험결과험증료해산법적유효성.