田攀 傅世勇 王红蕾
摘 要：该文从城市配送中装卸过程对配送的影响入手，研究了多车零担配送时的装箱组合问题，将货物在满足车辆容积和载重的情况下，采用聚合性层次聚类算法，根据配送目的地的相对距离将货物组合配送，从而减少装卸顺序对车辆的装载率影响，同时提高灵活性以应对交付问题，并使用算例进行模拟验证。为城市配送的配装组合提供了一个新的解决思路。
关键词：城市配送 车辆路径优化 货物配装 层次聚类算法
中图分类号：F259 文献标识码：A文章编号：1672-3791（2020）10（b）-0222-06
Abstract： This article starts with the impact of the loading and unloading process on distribution in urban distribution， and studies the packing combination problem of multi-vehicle less-than-carload distribution. When the goods meet the vehicle volume and load， the aggregate hierarchical clustering algorithm is adopted. The relative distance of the destination is used to combine and deliver the goods， thereby reducing the impact of the loading and unloading sequence on the loading rate of the vehicle， and at the same time increasing the flexibility to deal with the delivery problem， and use calculation examples for simulation verification. It provides a new solution for the combination of urban distribution.
Key Words： Urban distribution; Vehicle routing optimization; Cargo distribution; Hierarchical clustering algorithm
货物配载问题（VFP，Vehicle Filling Problem）是一个经典的复杂问题[1]。有大量对装箱问题的专门研究，其主要方向是在如何提高车辆运载运力的利用率方向。除了对空间或者载重的利用率，在实际使用过程中还会面临车辆路径优化问题，因为一旦装载完成，车辆所经历的送货点就已经固定，因此将货物配载问题与车辆路径优化问题组合起来研究被认为是一个更为贴近实际使用的研究方向[2]。尽管研究文献十分丰富，但很少会考虑到卸货优先级对优化结果的影响，而卸货过程在城市配送的物流场景中对效率、成该的占比是很大的。配载问题通常采用数学规划法求解[3]，但是如果模型太简单则不能对问题进行有效描述，而模型过于复杂又无法求解，配载的复杂性导致目前还很少有完全自动化的配载系统[4]。所以，该文没有直接研究装卸顺序的算法，而是从消除装卸顺序负面影响的角度来研究在城市配送场景下的配载问题。
1 问题描述
很多涉及车辆路径问题的算法，是聚焦于总里程的节省，重要的原因之一就是里程长短不仅意味着时效性，而且还涉及能源消耗。但城市配送有着自身的特点。城市配送运输里程短，即便在大中型城市配送距离，单次配送里程大多也在80km以内。相比干线与支线几百上千公里的配送距离，城市配送中距离对在配送成该的影响比例不大。特别是各大城市推行货车电动化之后，能源消耗的费用占比大幅下降，追求最小里程的经济效益进一步降低。而城市配送在装卸环节的成该占比要高很多，第一，大量存在多點配送，装卸总耗时占比很大，装卸用时摊销到车辆使用成该以及人工成该上时，装卸所占的成该是很高的。第二，城配过程中大量存在手工装卸，相比支干线的配送中心的机械化装卸，这种方式不仅耗时，而且对司机提出了更高的体力要求。城市配送中装卸的配送相比不管装卸的配送价格要高很多。第三，装卸环节可能产生货损。城市配送大多采用箱式货车，封闭式的箱体导致卸货必然遵循先卸货接近门口的位置，而且如果卸货优先级没有设置好，导致先配送的货物在不能直接装卸的位置，就可能需要将阻挡的货物先卸货，将配送的货物拿出来之后，再将之前的货物重新装箱，不仅耗费司机精力，重复装卸还可能导致货损。
因为卸货顺序实际上是决定了车辆的行车路径，所以通常装车时就必须考虑行车路径的影响。进一步来说，按照总路径最小的目标来摆放货物，要么可能装卸不方便，要么方便装卸方便但是影响了车辆的装载率，毕竟提高装载率对货物的摆放方式是有一定要求的。如果从便于装卸和提高装载率的角度出发，送货路径就可能与设计的最短路径出现偏差。因此即便综合优化方式能够实现路径和装载率的最优，仍然存在最佳卸货顺序与最短行车路径不一致而导致无法在实际情况下执行的可能。
货物的装卸难度很难通过程序量化，所以到底是牺牲运输里程还是选择更多的装卸，通过算法难以权衡，只能让人看到实物之后依靠经验衡量，所以很多城配企业更愿意选择人工调度的方式来完成。但是靠人工的方式，企业的配送规模就很难扩大，这也是城配市场碎片化的原因之一。
如果单台车辆配送货物的配送地点不用为了“顺路”而导致送货地点分散，而让送货地点集中的货物组合起来进行配送，则可能带来两个方面的好处：一方面配送目的地的聚集，能让司机在装卸过程中不大会受到配送顺序的制约，从而可以尽可能考虑装载率。另一方面一旦收货方因为某种原因出现无法马上收货，司机可以灵活地选择下一个配送地点，而不用付出太多的往返里程代价。特别是交付的货物中含有延迟惩罚条款时，由于司机能更换交付顺序来保证货物的准时交付，所以能够有机会提升整体客户满意度。尽管这种方式可能不是总路径最短的最优解，由于送货点尽可能的集中，考虑到城市配送距离已经较短，因此送货点之间是否顺路影响很小，可以视为综合情况下的满意度，因而在实际操作中会具有更高的适应性和灵活度。
2 城配零担配送的数学模型
该文研究的场景，是单个配送中心向城市多个地点的零担货物配送的情况，可以转化成如下描述。
某城市的物流配送中心有若干件待配送货物，配送中心有配送车辆若干，要求将这批货物在当日配送完毕，使花费的配送车次最少，且单个车次配送的货物目的地尽可能的集中。为什么不用车辆而用车次，是因为在城市配送中，为了提高车辆利用率，一般每天车辆都需要配送2～3次，因此用车次更符合实际情况。
在这个问题中，我们假设货物均可以混装，每个货物的体积和重量都小于单台货车的容积和载重，且装载的过程中只考虑配送车辆的载重和容积的限制。涉及的变量定义如下。
待配送有n个货物，i，j为货物的编号，i，j∈n;dij为货物i和货物j配送目的地之间的距离;wi，wj为第i和第j个货物的重量，vi，vj为第i和第j个货物的体积;假设所有的配送车辆车型一致，车辆的最大载重为Wc，最大容积为Vc;最终需要使用m趟车次完成配送，k为车次的编号，k∈m;xik为0，1变量，第i个货物由第k车次的货车负责，则xik=1，否则xik=0。
在尽可能聚集的情况下，优先选择车次最少的方案，然后根据聚集指数优中选优。
3 城配零担配送的算法设计
层次聚类是一种树形聚类方式。按照构建树形结构的方式不同，可以将聚类分为自顶向下和自底向上两种构建方式，分别称为聚合型层次聚类（Agglomerative Hierarchical Clustering）与分裂型层次聚类（Divisive Hierarchical Clustering）。聚合型层次聚类，也称自底向上的方法，首先将每一个样该都称为一个聚类簇，然后计算簇间的相似度，分层合并，直到最后只有一个簇为止或满足一定的终止条件[6]。采用聚合性层次聚类算法，对目的地之间的距离相近的货物优先进行组合，直至达到货车的装载上限。最初每个货物都只装入一台货车，每台车视为一个簇，然后根据距离情况逐步合并用车，即形成新的聚类簇。即当两个车（簇）中的两个货物目的地的距离，小于其他任意两个车中货物目的地距离，则可以说这两个簇（或者说两批货物的目的地）最为集中。在这两台车的装载货物之和没有超过单台货车载重或者容积的情况下，两批货物可合并放入一台货车，即形成新的聚类簇。新的聚类簇继续放回矩阵参与送货距离的检查，直至所有的簇的两两组合均会超过单车的容积或者载重为止。调整初始组合，寻找更多组合的可能，选择最优方案。具体算法设计如下。
步骤1：计算所有货物目的地之间的距离，构成距离矩阵。
步骤2：在距离矩阵中寻找最小的值。假设di1j1最小，则判断两个货物组合是否超出货车容积或者载重。如果已经超过，则继续寻找次小值继续检查组合可能性。如果并未超过，则两个货物可以组合装车。此时将合并后的车辆（新簇）放回矩阵参与计算，此时新的车辆所经过的送货点与其他车辆途径的送货点的距离会有两个：一是货物i1与其他货物的送货距离，二是j1与其他货物的送货距离，二者取最大值放回矩阵。
步骤3：迭代计算，直至所有簇无法继续合并。根据此时每台车辆中放置货物的编号，即可得出装配方案。记录此时所需的车次和聚集指数。
步骤4：更换合并簇的起始点为次小距离，其他条件不变。假设di2j2为仅次于di1j1的最小距离。则从i2与j2两个货物的合并开始判断。之后的判断均从不低于次小距离的两个簇开始组合，直至最大距离的簇，如果最小距离的两个簇没有在合并簇的过程中消失掉，则考虑最小距离的组合可能。记录此时的方案和性能参数。通过这种方式在多个可能中寻找最佳方案。
步骤5：继续更换合并簇的起始点到第三短的距离开始计算，以此类推，直至起始距离大于r。由于大于r的聚积意义已经不大，优先组合的方式找出最佳方案的可能性很低，从降低计算复杂度的角度不再继续迭代搜寻。最后在车次最少的方案中挑选出index最低的方案作为最终方案。具体流程图见图1。
4 算例模拟
以某市某日某物流園的某物流配送企业数据为例，该物流公司的车辆均为4.2m箱式货车，每辆车的载重为2t，容积在15m3，考虑到车辆一般无法刚好满载，设置90%为目标装载在率，即不超过13.5m3的容积，r设置为20km。
待送货物根据送货地点进行合并之后，一共40个送货点，每个点的经纬度坐标以及待送的货物体积和重量具体见表1。
通过Python实现算法最优解需5台车完成配送，聚积指数为141.917780，方案呈现出较好的聚积效果，如组合方案见表2，送货地点分布与装车信息见图2。
5 结语
该文从城市配送的装卸问题入手，研究了多车零担配送的配装问题。通过采用聚合性层次聚类算法，减少因装卸顺序带来的负面影响，提高了交付不确定的应对灵活性，希望能为城市物流配送面临的问题提供新思路。
参考文献
[1] 陆江.基于虚拟物流平台的多约束配车模型研究[D].北京邮电大学，2018.
[2] 胡振威.共享经济模式下城市配送车辆调度问题研究[D].西南交通大学，2018.
[3] 李飞.基于层次聚类的生物数据特征选择算法的研究与实现[D].吉林大学，2019.
[4] 尹超.城乡商贸物流服务网络资源优化研究[D].北京交通大学，2019.
[5] 蔡文清.浅析零散物流现状[J].西部皮革，2017，39（10）：72.
[6] 邓式阳.基于逻辑Petri网的Web服务组合与优化方法研究[D].山东科技大学，2019.
