-
摘要: 为求解带时间窗约束的配送中心车辆调度问题, 运用蚁群算法把时间窗约束转化为惩罚函数形式, 将其并入目标函数后, 建立了满足客户配送时间要求条件下的运输费用最低的车辆调度模型, 提出了模型的求解程序, 并以某算例进行了仿真分析。分析结果表明: 该模型通过参数的不同标定, 可以转化成旅行商模型、硬时间窗或软时间窗的车辆调度模型; 仿真算例中, 配送路线最优行驶距离为794 km, 车辆最长行驶时间为8.2 h, 该算法能有效求解配送中心车辆调度问题。Abstract: In order to solve vehicle scheduling problem with time windows for distribution centers, time window constraint was transformed into penalty function based on ant colony algorithm, and penalty function was added to objective function.A vehicle routing model based on minimum transportation cost was built up to meet the customer requirements of delivery times, its solving program was designed, and a simulation example was studied.Analysis result indicates that the model can be transformed into traveling salesman problem (TSP) model and vehicle scheduling problem (VSP) model with hard-time window or soft-time window through different parameter calibrations.The optimal driving distance is 794 km, and the longest vehicle diving time is 8.2 h in the simulation example, so the ant colony algorithm can effectively solve the scheduling problems of distribution centers.
-
表 1 需求点的参数
Table 1. Parameters of demand points
需求点 所需数量 需求点位置 卸货时间/min 时间窗 x坐标/km y坐标/km TEi TLi 1 120 30 114 25 0.5 4.0 2 200 40 36 40 0.5 4.0 3 120 48 96 25 1.5 10.5 4 150 52 120 35 1.5 5.5 5 140 92 114 30 0.5 1.5 6 60 92 66 20 1.5 10.5 7 110 94 100 25 1.5 10.5 8 180 108 134 35 0.5 3.5 9 90 44 160 20 0.5 1.5 10 160 20 54 35 0.5 3.5 11 140 108 32 30 1.5 6.0 12 150 130 88 30 1.5 10.5 
下载: 导出CSV
-
[1] LAPORTE G. The vehicle routing problem: an overview ofexact and approxi mate algorithms[J]. European Journal ofOperational Research, 1992, 59 (3): 345-358. doi: 10.1016/0377-2217(92)90192-C [2] 刘霞, 齐欢. 带时间窗的动态车辆路径问题的局部搜索算法[J]. 交通运输工程学报, 2008, 8 (5): 114-120. http://transport.chd.edu.cn/article/id/200805023LI U Xia, QI Huan. Local search alogrithm of dynamic vehiclerouting problem withti me window[J]. Journal of Traffic andTransportation Engineering, 2008, 8 (5): 114-120. (in Chinese) http://transport.chd.edu.cn/article/id/200805023 [3] 龚延成, 郭晓汾, 尤小玲, 等. 基于遗传算法的物流配送车辆调度问题研究[J]. 数学的实践与认识, 2004, 34 (6): 93-97. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htmGONG Yan-cheng, GUO Xiao-fen, YOU Xiao-ling, et al. Solving the vehicle routing and scheduling problems bygenetic algorithms[J]. Mathematics in Practice and Theory, 2004, 34 (6): 93-97. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htm [4] 赵建有, 吴利清, 刘大学. 带时间窗车辆路径问题的启发式遗传算法[J]. 交通运输工程学报, 2008, 8 (1): 113-117. http://transport.chd.edu.cn/article/id/200801022ZHAOJian-you, WU Li-qing, LIU Da-xue. Heuristic geneticalgorithmof vehicle routing problem with ti me windows[J]. Journal of Traffic and Transportation Engineering, 2008, 8 (1): 113-117. (in Chinese) http://transport.chd.edu.cn/article/id/200801022 [5] 段海滨, 马冠军, 王道波, 等. 一种求解连续空间优化问题的改进蚁群算法[J]. 系统仿真学报, 2007, 19 (5): 974-977. doi: 10.3969/j.issn.1004-731X.2007.05.010DUAN Hai-bin, MAGuan-jun, WANG Dao-bo, et al. Improvedant colony algorithmfor solving continuous space opti mizationproblems[J]. Journal of System Si mulation, 2007, 19 (5): 974-977. (in Chinese) doi: 10.3969/j.issn.1004-731X.2007.05.010 [6] 张宗永, 孙静, 谭家华. 蚁群算法的改进及其应用[J]. 上海交通大学学报, 2002, 36 (11): 1564-1567. doi: 10.3321/j.issn:1006-2467.2002.11.007ZHANG Zong-yong, SUN Jing, TAN Jia-hua. Applicationof thei mproved ant colony algorithm[J]. Journal of ShanghaiJiaotong University, 2002, 36 (11): 1564-1567. (in Chinese) doi: 10.3321/j.issn:1006-2467.2002.11.007 [7] DORIGO M, BONABEAU E, THERAULAZ G. Ant algo-rithms and stigmergy[J]. Future Generation ComputerSystems, 2000, 16 (8): 851-871. doi: 10.1016/S0167-739X(00)00042-X [8] DORIGO M, GAMBARDELLA L M. Ant colonies for thetraveling salesman problem[J]. Biosystems, 1997, 43 (2): 73-81. [9] JAYARAMAN V K, KULKAMI B D, KARALE S, et al. Ant colony framework for opti mal design and scheduling ofbatch plants[J]. Computers and Chemical Engineerivg, 2000, 24 (8): 1901-1912. [10] CALVETE HI, GALE C, OLI VEROS MJ, et al. A goalprogramming approach to vehicle routing problems with softti me windows[J]. European Journal of OperationalResearch, 2007, 177 (3): 1720-1733. [11] 吴云志, 乐毅, 王超, 等. 蚁群算法在物流路径优化中的应用及仿真[J]. 合肥工业大学学报: 自然科学版, 2009, 32 (2): 211-214. https://www.cnki.com.cn/Article/CJFDTOTAL-HEFE200902018.htmWU Yun-zhi, YUE Yi, WANG Chao, et al. Application andsi mulation of the ant colony optimization algorithm in logisticspath optimization[J]. Journal of Hefei University of Technology: Natural Science, 2009, 32 (2): 211-214. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HEFE200902018.htm [12] 张毅, 梁艳春. 基于选路优化的改进蚁群算法[J]. 计算机工程与应用, 2007, 43 (2): 60-63. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200702017.htmZHANG Yi, LI ANG Yan-chun. I mproved ant colony opti mi-zation algorithm based on route opti mization[J]. ComputerEngineering and Applications, 2007, 43 (2): 60-63. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200702017.htm [13] 刘利强, 戴运桃, 王丽华. 蚁群算法参数优化[J]. 计算机工程, 2008, 34 (11): 208-210. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200811076.htmLI U Li-qiang, DAI Yun-tao, WANG Li-hua. Ant colonyalgorithm parameters opti mization[J]. Computer Engineering, 2008, 34 (11): 208-210. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200811076.htm [14] 修桂华, 王俊鸿. 求解带硬时间窗车辆路径问题的自适应蚁群算法[J]. 计算机应用与软件, 2008, 25 (11): 109-111. https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ200811043.htmXI U Gui-hua, WANG Jun-hong. Adaptive ant colony opti-mization algorithm for solving vehicle routing problem withhard ti me windows[J]. Computer Applications and Software, 2008, 25 (11): 109-111. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ200811043.htm -
点击查看大图
图(2) / 表(1)
计量
- 文章访问数: 706
- HTML全文浏览量: 89
- PDF下载量: 651
- 被引次数: 0
