基于遗传算法的电子商务物流配送研究

《基于遗传算法的电子商务物流配送研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第３０卷第１期青岛大学学报（工程技术版）Ｖｏｌ．３０Ｎｏ．１２０１５年３月ＪＯＵＲＮＡＬＯＦＱＩＮＧＤＡＯＵＮＩＶＥＲＳＩＴＹ（Ｅ＆Ｔ）Ｍａｒ．２０１５文章编号：１００６－９７９８（２０１５）０１－００８１－０７；ＤＯＩ：１０．１３３０６／ｊ．１００６－９７９８．２０１５．０１．０１７基于遗传算法的电子商务物流配送研究付瑞，张纪会（青岛大学复杂性科学研究所，山东青岛２６６０７１）摘要：针对电子商务在物流配送中存在的问题，本研究以车辆可行驶最大路程为限制条件，将遗传算法与节约算法相结合，利用节约算法产生遗传算法的初始解，构造

2、节约遗传算法解决电子商务环境下的物流配送路径优化问题。仿真结果表明，节约遗传算法比遗传算法更具有全局最优性，求得最短路径的效果明显高于遗传算法；随着进化代数的增加，两种算法都越来越趋向于最优值，节约遗传算法的进化起点远高于遗传算法的进化起点，其最优值比遗传算法最优值好；节约遗传算法中的进化代数和种群规模对算法的性能有一定的影响；有路程限制与无路程限制所取得的货车运行路线不同，车辆的最大运行距离也不同。该研究可以提高物流配送效率、缩短配送距离，对节约物流成本和提高客户服务水平具有重要意义。关键词：物流配送；车辆路径问题；节约

3、算法；基于遗传算法的节约遗传算法中图分类号：Ｆ２５２．２；Ｆ７２４．６；ＴＰ１１文献标识码：Ａ［１］车辆路径问题（ｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ，ＶＲＰ）是一个典型的ＮＰ难问题，它在计算机科学、运筹学及工程优化等领域都有着广泛的应用。解决ＶＲＰ问题的算法主要有精确算法、传统启发式算法、模拟算法和［２］人工智能算法。精确算法采用数学规划方法求得路径最优解，其适用于求解小规模ＶＲＰ问题；传统的启［３］发式算法是指在可接受的计算时间、占用空间等开销的前提下，给出待解决的组合优化问题的一个可行［４］［５］解；模拟算法通

4、过计算机模拟实验取得车辆路线的优化解；人工智能优化算法通过揭示和模拟自然现象来求得问题的最优解。它具有全局优化性能、鲁棒性强、通用性强且适于并行处理等特点，广泛应用于求解［６］大规模ＶＲＰ问题。电子商务是利用现代信息技术处理现金流和物流，从而实现交易的一种商务活动。在电子商务环境下，物品能否准确无误地到达客户点是提升公司形象的关键要素，因此，如何高效选取解决车［７－９］辆路径问题的算法是目前亟待解决的问题。本研究将遗传算法与节约算法相结合，构造节约遗传算法研究电子商务环境下的物流配送路径优化问题，并在仿真环境下对所获得的最

5、优路径进行实验验证，仿真结果验证了该算法的有效性。该研究提高了物流配送效率，可以快速有效的满足客户需求。１问题描述电子商务环境下，物流配送路径优化问题可描述如下：根据电子商务企业某个时段顾客的商品订购情况，获取每个客户的货品需求量，确定该时段的实际配送网络，通过优化设计一套车辆配送路径，在满足各种限制条件下完成顾客要求的配送任务，使配送总费用最小。本研究以车辆可行驶最大路程为限制条件，将节约算法与遗传算法相结合求解车辆行驶的最优路径。收稿日期：２０１４－０７－１７；修回日期：２０１４－１０－１０基金项目：国家自然科学基金项

6、目资助（７０６７１０５７）；山东省自然科学基金项目资助（ＺＲ２０１０ＧＭ００６）作者简介：付瑞（１９９０－），女，山东潍坊人，硕士研究生，主要研究方向为物流与供应链管理。通讯作者：张纪会（１９６９－），男，山东青岛人，教授，主要主要从事现代启发式算法与应用、智能生产计划与调度、物流与供应链管理等方面的研究工作。Ｅｍａｉｌ：ｚｈａｎｇｊｉｈｕｉ＠ｑｄｕ．ｅｄｕ．ｃｎ８２青岛大学学报（工程技术版）第３０卷配送人员带着清单从配送中心出发，到各个已知坐标的客户点配送货物，当行驶总距离超过货车可行驶最大距离时，则回到配送中心处加油，

7、然后从配送中心继续行驶到下一个待服务客户处进行货物配送，直到服务完所有客户，最后车辆驶回配送中心。１．１模型假设１）只有一个中心站点，此中心站点提供供货服务和加油服务。２）中心站点与各个客户的位置坐标已知。３）每个客户点的需求量已知。４）整个区域内只有１辆货车供货。５）车辆在配送过程中的行驶距离之和不得超过其最大可行驶距离。６）每个客户被访问有且只能访问一次。７）必须满足每个客户的配送需求。１．２模型建立每个客户ｉ的表示方式为ｐｉ＝ｐ（ｘｉ，ｙｉ），ｉ＝１，２，…，Ｎ式中，ｘｉ表示客户ｉ所在点的横坐标；ｙｉ表示客户ｉ所在点

8、的纵坐标；Ｎ为这一区域内需要服务的客户数量。由于每个客户的坐标点已知，所以任意２个客户之间的距离已知。定义决策变量为１，车辆通过（ｉ，ｊ）ｘｉｊ＝｛０，否则式中，（ｉ，ｊ）表示车辆从客户ｉ行驶到客户ｊ。１）计算可行驶最短路径的目标函数，即ＮＮＤ＝ｍｉｎ∑∑ｄｉｊｘｉｊ＋ｄ１ｏ＋ｓｏ＋ｄｎｏ（１）ｉ＝１ｊ