PDF(685 KB)
PDF(685 KB)
PDF(685 KB)
基于模拟植物生长算法的车辆调度问题
Vehicle scheduling problem based on plant growth simulation algorithm
基于配送企业车辆资源的限制和客户需求时间窗的要求, 在考虑外包车辆和配送人员加班的情况下, 对带时间窗的车辆调度问题进行扩展研究. 根据客户需求的随机性特点构建以最小化车辆配送总成本为目标的机会约束规划模型, 并设计求解该问题的模拟植物生长算法. 结合车辆调度具体实例, 将模拟植物生长算法与遗传算法进行比较, 结果表明该算法不仅可以获得最优解, 而且提高了求解效率, 是一种有效的方法.
Based on the limit of the distribution enterprises' vehicle resource and the demand of customers' time windows, the paper gives an extensive research on the vehicle scheduling problem with time windows, which considers the situation of using outsourced vehicles and overtime for drivers. According to the stochastic demand of the customers, a chance-constrained program model was bulit to optimize the total cost of vehicle scheduling problem. A solution method-plant growth simulation algorithm (PGSA) is presented. Then, by means of calculating of the example and comparing with genetic algorithm, the results show that the optimum can be reached, meanwhile the efficiency of the presented algorithm is better than the genetic algorithm.
车辆调度 / 外包车辆 / 加班 / 模拟植物生长算法 {{custom_keyword}} /
vehicle scheduling / outsourcing vehicle / overtime / plant growth simulation algorithm {{custom_keyword}} /
[1] Dantzig G B, Ramser J H. The truck-dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] Yang-Byung P. A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines[J]. International Journal of Production Economics, 2001, 73(2): 175-188.
[3] Qureshi A G, Taniguchi E, Yamada T. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(6): 960-977.
[4] Osman I H. Meta-strategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Operations Research, 1993, 41(3): 77-86.
[5] Schulze J, Fahle T. A parallel algorithm for the vehicle routing problem with time window constraints[J]. Annals of Operations Research, 1999, 86(0): 585-607.
[6] 唐俊. 时间窗约束下的配送车辆调度问题研究[J]. 计算机工程与应用, 2011, 47(21): 243-245.Tang Jun. Study on vehicle routing problem with time windows[J]. Computer Engineering and Applications, 2011, 47(21): 243-245.
[7] Zäpfel G, Bögl M. Multi-period vehicle routing and crew scheduling with outsourcing options[J]. International Journal of Production Economics, 2008, 113(2): 980-996.
[8] 封全喜, 刘诚. 基于混合遗传算法的物流配送模糊车辆调度问题研究[J]. 长沙交通学院学报, 2005, 21(3): 78-82.Feng Quanxi, Liu Cheng. Hybrid genetic algorithm for fuzzy physical distribution vehicle scheduling problem[J]. Journal of Changsha Communications University, 2005, 21(3): 78-82.
[9] 魏明, 靳文舟.求解车辆路径问题的离散粒子群算法[J]. 计算机科学, 2010, 37(4): 187-191.Wei Ming, Jin Wenzhou. Discrete particle swarm optimization algorithm for vehicle routing problems[J]. Computer Science, 2010, 37(4): 187-191.
[10] Stewart W R, Golden B L. Stochastic vehicle routing: A comprehensive approach[J]. European Journal of Operational Research, 1983, 14(3): 371-385.
[11] Kenyon A S, Morton D P. Stochastic vehicle routing with random travel times[J]. Transportation Science, 2003, 37(4): 69-82.
[12] 魏明, 靳文舟, 孙博. 随机旅行时间的区域公交车调度模型及算法[J]. 公路交通科技, 2011, 28(10): 124-129.Wei Ming, Jin Wenzhou, Sun Bo. Model and algorithm for regional bus scheduling with stochastic travel time[J]. Journal of Highway and Transportation Research and Development, 2011, 28(10): 124-129.
[13] 李彤, 王春峰. 求解整数规划的一种仿生类全局优化算法——模拟植物生长算法[J]. 系统工程理论与实践, 2005, 25(1): 76-85.Li Tong, Wang Chunfeng. A global optimization bionics algorithm for solving integer programming —— Plant growth simulation algorithm[J]. Systems Engineering —— Theory & Practice, 2005, 25(1): 76-85.
[14] 王淳, 程浩忠. 模拟植物生长算法及其在输电网规划中的应用[J]. 电力系统自动化, 2007, 31(7): 24-28.Wang Chun, Cheng Haozhong. A plant growth simulation algorithm and its application in power transmission network planning[J]. Automation of Electric Power Sydtems, 2007, 31(7): 24-28.
[15] 李彤, 王众托. 模拟植物生长算法在设施选址问题中的应用[J]. 系统工程理论与实践, 2008, 28(12): 107-115.Li Tong, Wang Zhongtuo. Application of plant growth simulation algorithm on solving facility location problem[J]. Systems Engineering —— Theory & Practice, 2008, 28(12): 107-115.
[16] 郗莹, 马良, 戴秋萍. 多目标旅行商问题的模拟植物生长算法求解[J]. 计算机应用研究, 2012, 29(10): 3733-3735.Xi Ying, Ma Liang, Dai Qiuping. Plant growth simulation algorithm for multi-criteria travelling salesman[J]. Application Research of Computers, 2012, 29(10): 3733-3735.
[17] 代颖, 马祖军. 应急物流系统中随机定位-路径问题[J]. 系统管理学报, 2012, 21(2): 212-218.Dai Ying, Ma Zujun. Stochastic location-routing problem in emergency logistics systems[J]. Journal of Systems & Management, 2012, 21(2): 212-218.
[18] 王东生, 曹磊. 混沌、分形及其应用[M]. 合肥: 中国科学技术大学出版社, 1995.Wang Dongsheng, Cao Lei. Chaos, fractals and their applications[M]. Hefei: Publishing Company of University of Science and Technology of China, 1995.
国家自然科学基金(61375003); 河北省自然科学基金(F2014402040); 河北省教育厅人文社会科学研究重大课题攻关项目(ZD201442)
/
| 〈 |
|
〉 |
