CAJ | 학술논문

时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关，还与所处的时段有关．对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法，直接推导出跨时段对应的车辆行驶时间．在此基础上建立了数学模型，并构造动态规划启发式算法进行求解．该算法能够通过设置参数H平衡求解质量和运行时间．通过对10组随机产生的数据进行测试，结果表明动态规划启发式算法能够在很短时间内改进最近邻算法．当H=2时，求解质量改进11％，平均运算时间为1．34秒；当H=3时，在不到2秒的运算时间内求解质量改进17％．
시변망락중차량재임의량절점간적행사시간불부여절점간적거리유관，환여소처적시단유관．대시변차량조도문제제출일충만족선입선출준칙적과시단처리방법，직접추도출과시단대응적차량행사시간．재차기출상건립료수학모형，병구조동태규화계발식산법진행구해．해산법능구통과설치삼수H평형구해질량화운행시간．통과대10조수궤산생적수거진행측시，결과표명동태규화계발식산법능구재흔단시간내개진최근린산법．당H=2시，구해질량개진11％，평균운산시간위1．34초；당H=3시，재불도2초적운산시간내구해질량개진17％．
The vehicle travel time in time varying network not only depends on the distance between the nodes but also the time of day. In this paper, we developed a method satisfying first-in first-out property to deal with time period（s） crossing. The travel time can be deduced with it directly. The problem was formulated and a novel dynamic programming heuristics was presented to solve it. The algorithm can balance solution quality and computation time with parameter H. From the simulation results on 10 randomly generated cases, the new method can greatly improve the solution of nearest neighborhood algorithm within a very short time. When H=2, the average solution is improved 11% while the computation time is 1.34s. It also can be improved 17% within less than 2s with H=3.