网上超市物流配送问题研究

王 堃 黄晓旭

华北电力大学经济与管理学院 北京 102206

网上超市物流配送问题研究

王 堃 黄晓旭

华北电力大学经济与管理学院 北京 102206

网上超市的物流配送问题是提高企业效率的关键。物流配送的优化问题，可以归结为车辆路径问题。本文以网上超市的物流配送为背景，对其车辆路径问题进行研究。本研究对网上超市优化配送路径、降低配送成本、提高物流管理水平，最终增加企业核心竞争力，具有重要价值。

物流工程；网上超市；车辆路径问题

一、引言

互联网自应用以来，就一直以其便利性和及时性获得大众的青睐。网上支付的便利化，以及B2C电子商务领域的迅猛发展，使得“网上购物”成为当下社会的一个日常活动。由于采购成本的降低，更多的居民开始把视线投向日常用品的购买，因此专门售卖日常用品和生鲜食品的电子商务网站，即“网上超市”，应运而生。对于如京东、美国亚马逊这类普通的网上零售商，每个订单仅包含有2～3件商品。而对于网上超市，平均每个订单包含7～8种商品、高达16.7件商品。网上超市的这些特性，决定了以往适用于普通网上零售的车辆路径问题的模型、算法等已无法满足其实际需要。因此更为复杂、但更贴合网上超市物流配送实际的车辆路径问题研究就成为了优化网上超市物流配送成本的关键。

现有研究主要集中于对网上超市产品的经济性的评价，以网上超市为应用背景的物流配送车辆路径问题的研究较少。近些年国外相关的研究有很多，较为相关的是Schönberger等人研究了一个只配送两种商品的CVRP，即将两个单独的VRP问题通过一个约束结合在一起，解决了一个包含有36个客户的问题，并针对不同的约束情况进行了对比试验，其结果表明其所采用的约束不影响配送路线的选择，而只影响配送的调度。

对两个车辆路径问题进行建模时，不仅要考虑单级车辆路径问题中的优化问题，还要考虑两个车辆路径问题的整体优化效果，因此其建模和求解过程将十分复杂。网上超市的特征更加剧了其物流配送的求解难度。已有的车辆路径问题的模型、算法等已无法满足其实际需要。需要提出一套适用于求解网上超市物流配送问题的方法，降低物流配送成本，提高订单履行效率。

二、问题描述

不同于传统的物流配送问题，对于网上超市而言，由于其订单中的商品种类多、数量大，是否对客户的订单进行拆分、在哪个阶段进行拆分对模型的建立及求解极为重要。考虑到拆分订单后多次配送会对客户的体验造成负面影响，同时客户对送货时间也存在要求，因此，网上超市物流配送问题实际上研究的是两个带时间窗及容量限制的车辆路径问题。问题可定义为：一个配送中心需要在指定的时间段内通过附近的中转站对多个客户进行送货，单个客户的需求量小于车载容量，供货点和中转站之间（第一级配送）在进行物流配送时允许对客户的订单进行拆分，而中转站到客户之间（第二级配送）在配送时不允许对订单进行拆分，不同的配送阶段所采用的车辆的容量不同，部分客户对送货时间存在要求，超过该要求顾客将拒绝收货。优化的目标是在满足车载容量的限制条件和顾客的硬时间窗要求下，以最小的成本进行配送。

三、求解算法

大型网上超市的应用背景，决定了本研究中的两个车辆路径问题的集成优化与其他两级车辆路径问题的研究相比难度很大。需要对客户点进行聚类，以缩减求解规模；分析两级车辆路径方案形成的规律，实现基于计算机的车辆路径方案的快速生成；构造高质量算法，对大规模车辆路径问题进行快速求解。

（一）遗传算法

遗传算法（Genetic Algorithm）是由Holland在1975年提出来，并首先由Lawrence J. Fogel应用于求解车辆路径问题的。遗传算法主要是模仿生物进化的过程，将初始可行解二进制化为所谓“基因”，并利用遗传和变异的思想对解进行优化。遗传算法是一种比较经典的智能优化算法，由于其收敛速度快而局部搜索能力弱，因此通常用来和其他局部搜索快的方法如禁忌搜索算法等相结合。

（二）邻域搜索算法

邻域搜索算法是一种经典的启发式算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。邻域搜索算法简单、灵活及易于实现，常被应用于计算机科学（主要是人工智能）、数学、运筹学、工程学、生物信息学中各种很难找到全局最优解的计算问题。

（三）算法步骤

初始解的确定对于启发式算法具有极重要的意义。好的初始解可以减少算法在寻路过程中所消耗的时间，提高在规定时间内满意解的质量。对于一般的模型，初始解的生成常采用随机生成的方法。然而，对于带时间窗的问题来说，随机生成的解通常无法成为可行解。在实际的物流配送过程中，存在着一些弹性较好的配送路线，这些路线可以在时间紧张或遇突发情况时保证配送的效率。本文结合实际情况，根据现有的一般配送路线对模型进行优化，可以大幅提高算法的效率。

Step1输入初始解{X,Y,Z}，并计算该情况下的目标函数H*，令k=0；

Step2对Z使用领域搜索得到新的Z，在该Z下应用遗传算法，在规定的迭代次数下得到新的满意解和目标函数Hk；

Step3若Hk≤H*，令H*=Hk，转Step 4；否则转Step4；

Step4若k=kmax，则计算结束，输出当前满意解；否则令k=k+1，转Step2.

四、结论

本文考虑网上超市的实际情况，建立了两级车辆路径问题的优化模型，并提出了针对两级车辆路径问题的协同优化的思想。该模型和思想结合算法程序及实际算例分析，将有助于解决网上超市物流配送成本难题，帮助网上超市企业更好更快发展。

[1]王艳玮,王拖拖,常莹莹．生鲜农产品网上超市物流配送模式选择研究[J]．经济与管理, 2013, 4: 69–74．

[2]SCHÖNBERGER J． The Two-Commodity Capacitated Vehicle Routing Problem with Synchronization[J]． IFACPapersOnLine, Elsevier Ltd．, 2015, 48(3): 168–173．