关键词：
无人配送
距离容量均受限
算法设计
近似比
车辆路径问题
摘要：
伴随城镇化进程的加快,同时为推进新冠肺炎疫情防控的需求,转变传统物流配送势在必行。无人配送作为现代物流的新兴形态,用机器代替人工或者人机协作实现物流配送,以达到提高效率和降低成本的目的。无人物流配送设备大致可分为无人配送车、无人机和配送机器人三种。论文研究无人物流配送问题,多辆满载容量C和满电行驶距离D都受限的无人物流配送设备,从单一仓储点出发前往客户点收取货物后返回,每个客户点货物仅由单辆无人物流配送设备收取一次。返回仓储点的设备能够在仓储点充电,但在收货期间只前往额外配备的充电站充电。问题可描述为给定部分点赋权、所有边赋权的完全图,客户点、仓储点以及充电站点构成图上点集合,连接客户点、仓储点以及充电站点构成边集。每个客户点上存放的货物重量表示其权重,其中每个客户点的权重小于等于无人物流配送设备的满载容量,所有客户点的权重总和大于无人物流配送设备的满载容量。每条边的距离表示其权重,其中边的距离满足三角不等式。在配送网络中未额外配备充电站的情况下,假定各点之间的距离小于等于αD/2,α∈（0,1）,极小化无人物流配送设备数目。构建数学模型并利用装箱问题的FFD算法以及贪婪的思想设计算法Ⅰ。根据客户点的重量,分情况分析了近似算法Ⅰ的近似比。当客户点货物重量满足c（u）＞αC,（?）u∈V∪{r},α∈（0,1）时,算法Ⅰ的近似比上界为[1/α];当客户点货物重量满足c（u）≤αC,（?）u∈V∪{r},α ∈（0,1）,且无人物流配送设备只前往[1/α]个客户点时,近似算法Ⅰ的近似比上界为3。假定w（u,v）≤αD/2,（?）u,v∈ V∪ {r},α ∈（0,1）,并引进参数β控制配送网络的大小。在配送网络中未额外配备充电站的情况下,极小化无人物流配送设备总配送距离。构建数学模型后设计近似算法Ⅱ,算法Ⅱ的近似比上界为β;在配送网络中额外配备充电站的情况下,客户点与其最近充电站的距离满足w（v,fv）≤αD/2,（?）v∈V,（?）fv ∈ F,极小化无人物流配送设备总配送距离。当无人物流配送设备在容量未满但电量将耗尽时,只能前往额外配备的充电站充电。构建整数规划数学模型,再设计近似算法Ⅲ,由哈密尔顿路、分割算法、指派算法以及添加回路构成算法Ⅲ,算法Ⅲ的近似比上界为2（1+α/1-α）β。在配送网络中额外配备充电站,且客户点之间距离不受限制,客户点与其最近充电站的距离满足于w（v,fv）≤αD/2,（?）v∈V,（?）fv ∈ F时,极小化无人物流配送设备总配送距离。由距离调整、哈密尔顿路、分割算法、指派算法以及添加回路构成近似算法Ⅳ,算法Ⅳ的近似比上界为（1+α/1-α）β。总之,论文研究三类无人物流配送问题,构建数学模型后设计近似算法,并分析了近似算法的近似比。
欢迎来到三峡大学图书馆！
