论文部分内容阅读
已有集散货物路径问题的研究主要考虑车辆的载重约束,但由于现实配送物品中,不少物品属于轻型货物,体积成为制约装载量的重要约束。若仅考虑重量约束而不考虑体积约束,将导致计划装车的货物无法放入车厢。本文针对此,研究了一类特殊的带体积约束的车辆路径问题——考虑二维体积约束的集散车辆路径问题(Vehicle routing problem of simultaneous deliveries and pickups with two-dimensional loading constraints,2L-CVRPSDP).该问题中的客户需求可简化为不同尺寸和不同重量的二维矩形,目标为在满足车辆载重和容积约束的情况下选择运输成本最小的路径。该问题可应用于轻型且不宜堆叠的货物配送中,如家电、玻璃制品及精密部件等易损、易碎物品的配送。本文建立了2L-CVRPSDP问题的数学模型,提出了解决该问题的一种改进的迭代局域搜索算法:首先使用改进的节约算法产生初始解,然后采用变邻域下降搜索改进当前解,若当前解没有改进,则采用重起和扰动策略,改变搜索方向继续迭代搜索,直到达到设定的迭代代数为止。其中,为了判断解的体积约束可行性,该算法嵌入了基于四种装配规则的二维装箱启发式算法。为了验证本文算法的有效性,首先在Iori的标准算例(用于2L-CVRP问题)的基础上,设计了2L-CVRPSDP的测试算例;通过实验确定了算法的相关参数,测试了扰动和VND对计算结果的影响;然后,测试了2L-CVRPSDP的特例2L-CVRP问题,并与相关文献比较,结果表明该算法更新了部分最好解,改进了文献最好解的平均值。进而,给出了2L-CVRPSDP的计算结果。此外,本文还应用该算法开发了一款考虑装箱约束的智能配送管理系统,实现配送路线的自动生成和优化,该系统操作简单、方便,可以根据用户需求快速的生成一种最佳配送路线方案,同时还可以把路线和箱子的装载位置直观的呈现给用户。本研究拓展了已有集散货物路径问题的研究,考虑了重量和体积的双重约束,增强了应用范围;开发的相应优化系统,能为物流配送提供重要的决策支持,进一步增强了实用性。