南京宁果集团基于时间窗配送线路优化设计

文 献 综 述

物流业作为当今经济发展的引导和支持性行业，越来越多的受到社会的关心与重视。虽然很多人听到”物流”第一反应就是交通运输的想法有些片面，但是作为企业的”第三利润源” ，物流费用50%都是由运费构成的。可以看出来运输费用对于企业控制物流成本起到了至关重要的作用。而在运输中的配送更加独特，它与长途运输有着不小的区别，有着小批量、多频次以及时间限制的的特点。

配送是物流基本职能之一，由于其能够很好的实现”门到门”的服务，并为用户所认可，近年来，得到充分的发展。但随着劳动力成本的上升、顾客分布及接受服务时间的不同，物流配送成本正逐年上升，限制了物流配送行业的发展。这就要求我们物流配送企业要设计出高效的配送线路。

配送企业对于配送线路的设计不仅要考虑到总配送路程，还要满足各个配送点的服务要求。从经济学角度看，降低成本与提高服务水平之间是”二律背反”关系(陈子侠，2007)^[1]。这一规律同样适用于配送企业，即若配送企业降低物流配送成本，服务水平会随之下降，提高配送成本，服务水平随之上升。配送企业不会为了绝对满足每一个配送点的时间等服务要求，盲目增多车辆与路线；也不会为了最大化降低成本，在无法满足时间要求的情况下只派一辆车、安排单一配送路线。所以如何安排配送车辆、如何设计配送路线，才能在配送成本与服务之间寻求一个平衡点，是一个值得研究、探索的问题。基于时间窗的物流企业配送线路优化可以最大限度的提高客户服务水平，并降低配送成本。

配送约束中的时间窗（Time Window）可以分为软时间窗和硬时间窗。软时间窗是指可以不在指定的时间范围之内服务，但是必须要赔偿对客户带来的损失。硬时间窗是指必须要在指定的时间范围内服务，否则予以拒绝服务。受客户时间限制，物流配送企业配送路径存在不确定性。将软时间窗加入到单一配送点，多线路问题中，即为本设计所要研究的问题。

我国目前的物流配送行业中，很多公司，尤其是中小型公司在配送路线设置方面存在着信息化程度低、技术性不强、企业自身利益最大化等弊端。我们需要针对这一问题利用现有的技术手段和数学方法来帮助公司更好地做配送路线的优化与设计，从而为企业选择更快捷的路径，控制更合理的成本，提供更好的服务。

提到物流配送路线问题，TSP问题是无法避开的，这是一个典型的NP难题。那么我先来介绍一下TSP（Travalling Salesman Problem）旅行商问题问题。该问题简单的说就是有一个旅行推销员要去到N个城市推销自己的产品，但是每个城市必须只经过一次，并且最终回到销售员的出发点。要求为该推销员选择路径，并在其中挑选出最短的一条路线。对于该难题的算法研究方面，Goldberg和Grefenstette首次使用遗传算法求解TSP问题，国内高经纬等人同样针对TSP问题进行了遗传算法的编程和求解，此外王银年、葛红伟二人综合运用了模拟退火算法与遗传算法，求出了比TSPLIB的实例中给出的最优的路径。当然还有许多有效、常用的算法，比如二叉树描述法、神经网络法等等。

通过参阅大量的文献资料，并对TSP问题与基于时间窗的物流线路优化设计问题进行对比分析，物流线路设计与优化是对于旅行商问题的升级。著名的TSP问题的国内外各种研究成果对于解决问题物流路线的设计起到了开拓和奠基的关键作用。为了更好地利用TSP问题成果借鉴、应用到配送问题，首先介绍一下TSP与物流配送路线二者的异同点。相同点：1.都需要考虑到路径的距离是否最短。2.路线都是从原点出发，并且最终回到原点的一个封闭图形。3.每个点必须只经过一次。不同点：1.TSP问题只是单一封闭路径最优化，而配送问题则是多条配送路径综合最优。2.TSP问题中的每个城市点没有对于旅行商的时间窗限制，而每个配送点都有一定的时间窗限制，必须满足否则会对服务质量造成损害。3.TSP问题每个点不需要对于货物量的要求，而配送则必须满足各个配送点的配送量的要求。

虽然配送线路优化问题的解决无法完全应用TSP的研究成果，但是我们可以对其中相同部分进行参考、应用，并加上我们自己的一些算法、设计，从而满足配送中特有的

特点与要求。