地球信息科学学报
地毬信息科學學報
지구신식과학학보
GEO-INFORMATION SCIENCE
2013年
6期
879-886
,共8页
校车调度问题%校车路径问题%带时间窗的车辆路径问题%模拟退火算法
校車調度問題%校車路徑問題%帶時間窗的車輛路徑問題%模擬退火算法
교차조도문제%교차로경문제%대시간창적차량로경문제%모의퇴화산법
school bus scheduling problem%school bus routing problem%vehicle routing problem with time win-dows (VRPTW)%simulated annealing
校车调度问题(SBSP)是通过调度使一辆校车服务完一个学校后继续服务其他学校,以减少一个地区所需的校车总数,进而降低校车采购成本和运营成本。目前的SBSP求解方法是将其转化为指派问题或运输问题,使用混合整型规划算法或者简单启发式算法进行求解,但求解性能有局限。本文在单校校车路径规划的基础上,将单校路径抽象为虚拟站点,进而将SBSP转换为带有时间窗的车辆路径问题(VRPTW),设计元启发算法进行求解。使用构造启发式算法获得初始解后,在模拟退火算法框架中通过典型的局部搜索算子搜索邻域解,逐步改善求解质量。搜索算子包括单点移动、两点交换、2-OPT和Cross-Exchange。迭代优化过程中以校车路径数为主要目标,路径长度为次要目标。为避免邻域搜索陷入局部最优,算法以一定的概率接受部分使路径长度增加的解。15个案例实验验证了本算法的有效性,与现有算法相比,能够获得更好的优化目标,适用于大规模的校车调度。
校車調度問題(SBSP)是通過調度使一輛校車服務完一箇學校後繼續服務其他學校,以減少一箇地區所需的校車總數,進而降低校車採購成本和運營成本。目前的SBSP求解方法是將其轉化為指派問題或運輸問題,使用混閤整型規劃算法或者簡單啟髮式算法進行求解,但求解性能有跼限。本文在單校校車路徑規劃的基礎上,將單校路徑抽象為虛擬站點,進而將SBSP轉換為帶有時間窗的車輛路徑問題(VRPTW),設計元啟髮算法進行求解。使用構造啟髮式算法穫得初始解後,在模擬退火算法框架中通過典型的跼部搜索算子搜索鄰域解,逐步改善求解質量。搜索算子包括單點移動、兩點交換、2-OPT和Cross-Exchange。迭代優化過程中以校車路徑數為主要目標,路徑長度為次要目標。為避免鄰域搜索陷入跼部最優,算法以一定的概率接受部分使路徑長度增加的解。15箇案例實驗驗證瞭本算法的有效性,與現有算法相比,能夠穫得更好的優化目標,適用于大規模的校車調度。
교차조도문제(SBSP)시통과조도사일량교차복무완일개학교후계속복무기타학교,이감소일개지구소수적교차총수,진이강저교차채구성본화운영성본。목전적SBSP구해방법시장기전화위지파문제혹운수문제,사용혼합정형규화산법혹자간단계발식산법진행구해,단구해성능유국한。본문재단교교차로경규화적기출상,장단교로경추상위허의참점,진이장SBSP전환위대유시간창적차량로경문제(VRPTW),설계원계발산법진행구해。사용구조계발식산법획득초시해후,재모의퇴화산법광가중통과전형적국부수색산자수색린역해,축보개선구해질량。수색산자포괄단점이동、량점교환、2-OPT화Cross-Exchange。질대우화과정중이교차로경수위주요목표,로경장도위차요목표。위피면린역수색함입국부최우,산법이일정적개솔접수부분사로경장도증가적해。15개안례실험험증료본산법적유효성,여현유산법상비,능구획득경호적우화목표,괄용우대규모적교차조도。
Given school bus trips for each school in a school district, if a school bus can serve multiple trips, the efficiency of school bus service can be improved in terms of the number of buses needed and the total travel cost. The school bus scheduling problem (SBSP), a class of school bus routing problem (SBRP), is concerned with assigning a fleet of buses to serve all the given trips and aims to get optimal bus schedules. Each school has its xed time window within which school bus must arrive at the destination school of the trip. In existing litera-tures, SBSP is usually formulated as a transportation problem (TP) or an assignment problem (AP). However, many existing algorithms for vehicle routing problem (VRP) have not been fully utilized to solve the problem ef-fectively. This paper proposes a meta-heuristic algorithm for large-scale SBSP. Treating a trip as a virtual stop with time window, the problem can be converted to a vehicle routing problem with time windows (VRPTW). Therefore, the SBSP can be solved in a VRP algorithm framework. After a set of feasible solutions are generated using construction heuristic algorithm, a simulated annealing (SA) algorithm is designed to improve the initial so-lutions iteratively. Four general operators for VRP, one-point move, two point move, two-opt move and cross-ex-change move, are used in the neighborhood search. In addition to the SBSP objectives of minimizing the number of the routes and the total travel distance, the sum of squared number of route stops is added as a new objective. This will guide the neighborhood search toward the situation that deleting some routes more easily. For avoiding local optimum, some worsening neighborhood solutions can be accepted with a certain probability. Computation-al tests on 15 instances with a homogeneous fleet show the effectiveness of the proposed approaches. Compared with the existing SBSP solutions, the proposed algorithm can solve large-scale SBSP in a reasonable time and find better solutions using fewer buses. In addition, the algorithm can be easily integrated with GIS for solving real world school bus scheduling.