基于遗传算法的接驳转运车辆排程的分析研究

摘　要：专业物流提供货物有效率地从供应商至客户间移动的服务，于接驳转运的配送活动上扮演着极重要的角色。本文建构了一种用于接驳转运规划模型求解的遗传算法，利用改进的配送模型和遗传算法进行接驳车辆配送方案的优化设计。

关键词：遗传算法，接驳转运
1．引言
　　目前国内进入全球市场的企业为满足全球顾客的需求，完善的配销规划显得格外重要，因此使得物流中心的重要性与日剧增，整合(物流、商流、金流、信息流)于一身的现代化物流中心，将是未来流通业发展的主流。为了迎接全球性竞争时代的来临，完善的物流系统，特别是仓储系统逐渐成为企业经营的成功关键，而配销中心正是流通产业的枢纽，若能适时提升其决策效能，必可掌握竞争优势。
　　所谓接驳式转运（Cross Docking）则是利用分布众多的供货商或是配销中心，整合固定地理范围的营业分公司订单以整合方式出货。这种接驳式转运必须在精准物流信息管理下才能得以进行，而为了要达到接驳式转运的运作效率，则必须要有一套规划完善的车辆运输安排，使得接驳式转运的精神得以发挥。由于接驳式转运是不将货物堆存在中转站点，因此各路线的运输车辆需要进行协调整合，使得货物能够在中转站点等候的的时间最短，让货物能够更快速的进行运输。
2．遗传算法在接驳转运模型中应用
　　遗传算法擅长解决的问题是全局最优化问题，它能够跳出局部最优而找到全局最优点。遗传算法其实是一种求函数极值的随机搜索算法，但它又不是毫无规则地随机搜索，而是基于一种假设：假设函数值的分布是有一定的连续性的，换句话说函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率。基于这个假设，遗传算法总是以较大概率保留较优值所代表的搜索方向，而以较低概率保留较差值所代表的搜索方向。
　　为了验证本文所建立的模型适用于大型网络，因此，本文以江苏XX物流有限公司计划于江苏地区的南、北两地，各设立一大型中转站点，并以轴辐式网络为其营运网络为例，作一实例分析。其中南部之中转站点设于南京；北部之中转站点则设在镇江，而营业分公司由南至北只抽取前八大的独立营业分公司，分别为常州、苏州、溧阳、扬州、淮安、盐城、连云港、徐州等八个营业分公司。
　　本文建立接驳转运中专业物流配送问题的模型，主要工作任务是为专业物流公司的货车的指派与货物配送路线的规划，本文所采用的XX公司的营运网络是以两个中转站点、八个营业分公司及单一车种形态为主，然而公司在不同之外部环境（如：市场压力、科技压力及社会压力等）改变下，亦会冲击供应链中专业物流公司内部相关决策的改变，而有不同的情境分析，因此，本文进一步探讨在外部环境的冲击下，相关参数的改变，如营业分公司、中转站点站所或车种的改变条件的下，对整个网络的变化，据以比较其与XX公司所实行的营运网络的差异，希望使本模型更具适用性。
　　由于本文的进站间距乘数kia与离站间距乘数kjd是以二幂策略为前提假设，因此在遗传算法当中的染色体所进行的染色体是以各进站与离站路线的乘数幂次进行编码，介绍本文的算法流程。
（1）产生初始母代。
（2）进行适应值评估。
　　2.1 进行染色体解码，获得各路线间距。突变点突变点
　　2.2 运用成本曲线中的各个断点，寻找对应此组染色体（路线间距乘数集合）的最佳基本周期值。
　　2.3 纪录各组路线间距的最小成本与其断点值，并将此最小成本设定为各染色体的适应值。
（3）设定终止条件，并开始演化：t ← t+1。
　　3.1 从母代挑选适应值较佳的染色体进入子代。
　　3.2 针对子代的染色体进行交叉。
　　3.3 针对交叉后的子代进行突变。
　　3.4 复制子代为母代，评估适应值。
　　3.5 子代的最佳解与目前的最佳解进行比较，并进行最佳解的更新。
　　3.6 是否到达终止条件
（4）演化结束，获得最佳解组合与最小化成本。
　　根据上述的遗传算法流程，本文将以此算法寻找出最小成本下的发车间距，并同时获得在各前后端路线分别派遣何种类型的车辆进行运输作业，使得此配销体系得以运作。
3．应用实例结果比较
　　对于GA参数的设定实验，该结果可提供往后运用GA求解本问题的实验参数设定的客观参考。为了寻求最佳的参数设定，这里暂举将100笔需求，利用传统的蚁群算法和贪婪算法进行比较，遗传代数皆设在500代；其实验结果如下：
表1.100笔需求的实验结果

演算方法 遗传算法(代数/母体数)蚁群算法(代数/蚂蚁数)贪婪算法500/50500/100500/101000/101000/50-载货量1134900135100128000127900127900115600载货量212720012650012510012520012560093700载货量312130012330012020011990012020094100平均量128300128300124433124333124567101133平均运算时间 (sec.) 8901786138028702955-RSQ 26.86%26.86%23.04%22.94%23.17%-

图1.100笔需求的改善比例结果
　　本文以对比其他两种算法来验证以遗传算法为基础的转运配送模型，遗传算法在不同回合数的结果与蚁群算法在不同代数及母体数下的结果的比较，可了解随着需求笔数的变化，三种算法所产生结果的差别。从实验结果可知遗传算法的平均产量无论在需求笔数多寡的状态下皆能优于其他的算法，虽然遗传算法的结果随着代数与母体数的调整会有所变动，不过遗传算法的结果大致上皆优于遗传算法及贪婪算法。
参考文献：
[1]张松艳,选择操作数与遗传算法的计算效率分析[J],宁波大学学报理工版,2009第22 卷第3 期,页374-377
[2]Alkens C H. Facility location mode1s for distribution planning. European Journal of Operational Research. 1985, 22 (3): 263-279.
[3]Taniguchi E. Optimal size and location planning of public logistics terminals. Transportation Research. 1999, 35E: 207-222.
[4]Holmberg K. Exact solution methods for incapacitated location Problem with convex transportation costs. European Journal of Operational Research. 1999, 114 (2): 127-140. 本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/242843.html