摘要
伴随城镇化进程的加快，同时为推进新冠肺炎疫情防控的需求，转变传统物流配送势在必行。无人配送作为现代物流的新兴形态，用机器代替人工或者人机协作实现物流配送，以达到提高效率和降低成本的目的。无人物流配送设备大致可分为无人配送车、无人机和配送机器人三种。 论文研究无人物流配送问题，多辆满载容量C和满电行驶距离D都受限的无人物流配送设备，从单一仓储点出发前往客户点收取货物后返回，每个客户点货物仅由单辆无人物流配送设备收取一次。返回仓储点的设备能够在仓储点充电，但在收货期间只前往额外配备的充电站充电。问题可描述为给定部分点赋权、所有边赋权的完全图，客户点、仓储点以及充电站点构成图上点集合，连接客户点、仓储点以及充电站点构成边集。每个客户点上存放的货物重量表示其权重，其中每个客户点的权重小于等于无人物流配送设备的满载容量，所有客户点的权重总和大于无人物流配送设备的满载容量。每条边的距离表示其权重，其中边的距离满足三角不等式。 在配送网络中未额外配备充电站的情况下，假定各点之间的距离小于等于αD/2，α∈(0,1)，极小化无人物流配送设备数目。构建数学模型并利用装箱问题的FFD算法以及贪婪的思想设计算法I。根据客户点的重量，分情况分析了近似算法I的近似比。当客户点货物重量满足c(u)＞αC,?u∈V∪{r},α∈(0,1)时，算法I的近似比上界为[1/α]；当客户点货物重量满足c(u)≤αC,?u∈V∪{r},α∈(0,1)，且无人物流配送设备只前往[1/α]个客户点时，近似算法I的近似比上界为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?α)β。 总之，论文研究三类无人物流配送问题，构建数学模型后设计近似算法，并分析了近似算法的近似比。
NETL