《基于时间窗的配送路线设计潘》由会员分享，可在线阅读，更多相关《基于时间窗的配送路线设计潘（14页珍藏版）》请在金锄头文库上搜索。
1、基于时间窗的配送路线设计研究潘志霄（南京工业大学 工业工程系，南京 210009）摘要：本文在配送线路设计中引入时间窗的概念，根据遗传算法和MATLAB相结合的方法，对配送线路进行优化设计。使得设计的配送线路方案更加贴近实际配送的真实情况，具有更高的应用价值。依据所收集的宁果集团的车辆、顾客分布、配送量、时间窗等数据进行建立数学模型，使用以上研究方法为该企业设计高效的配送线路，并且解决了以下3个问题：1. 降低企业的配送成本；2. 缩短车辆的行驶路程；3. 满足顾客时间窗的要求。关键词：时间窗；配送线路；遗传算法；优化设计0 前言配送是物流基本职能之一，由于其能够很好的实现“门到门”的服务，并
2、为用户所认可，近年来，得到充分的发展。我国发展物流配送相对于国外一些发达国家还是比较迟的1。通过90年代以来的商品流通，相关政府部门认识到配送是一种很好的物流方式，很多城市的物资部门设立了配送中心，送货上门得以成为现实，为企业配送所需的生产资料提供了极大地便捷。随着人们对于物流的关注，物流配送在城市日益得到了重视和发展。相继有许多城市的公司建立了城市配送中心、物流基地，并且相关的设施配套齐全，机械化程度提高。这都为公司向客户提供“门到门”的配送服务打下了坚实的基础。但随着劳动力成本的上升、顾客分布及接受服务时间的不同，物流配送成本正逐年上升，限制了物流配送行业的发展。1 基于时间窗的配送路线1
3、.1 配送配送是指在一定的经济区域内，对商品进行加工、包装、拣选、装配等，并且按照规定的时间将这些商品送到指定的地点的物流活动2。其具有以下特点：（1）提供给用户的终端运输服务。配送是一种基于配送中心物流节点向顾客提供的商品运输服务。货物运输分为干线和支线运输。干线运输就是我们熟知的长距离、大批量的运输，而支线运输主要就是指干线运输完成到当地配送中心之后，进一步将商品通过配送的方式送到具体的顾客的最末端的物流服务。（2）注重时效性和合理性。配送的一个重要的特点就是个性化服务，可以根据不同顾客的需求，提供差异化的服务。配送有效的将“配”与“送”巧妙地结合，并且依据顾客对于时间、地点的要求，制定出
4、合理地配送计划，而其中最核心的就是车辆、线路的安排。（3）强调系统化、一体化。用户对于配送的印象可能仅仅是送货的车辆、送货的人员，而配送远远不止这些。配送是和采购管理、销售管理、信息管理、财务管理、仓库管理等各个部门密不可分的，任何一个环节出现差错，都会导致配送活动无法顺利完成。比如销售部门未与采购部门沟通到位，很可能导致缺货现象，一旦有客户购买该商品，仓库无货就无法准时送达。所以配送与其他只能部门是系统化、一体化的组合，不可以割裂地看待3。1.2 基于时间窗的配送车辆线路基于时间窗的配送路线的设计是指配送中心既需要满足用户的需求量的要求，又要在用户指定的时间内将货物送至用户而进行的配送线路的
5、优化设计过程。在这一过程之中，配送企业需要考虑到自身经济效益、顾客需求和效率等多方面的因素4。带有时间窗的配送车辆线路的研究源于在1959年Danting和Ramser 提出的车辆路径问题，即VRP(Vehicle Routing Problem)而带有时间窗的车辆路径问题(VRPTW Vehicle Routing Problem with Time Window) 是在VRP的基础上加人了顾客访问时间窗口约束， 这一约束使得问题的描述更贴近物流配送的现实情况。1.3 遗传算法遗传算法是从达尔文进化论中得到的灵感和启发，借鉴自然选择和自然进化的原理，模拟生物在自然界中的进化过程而形成的一种优
6、化求解方法5-6。遗传算法解决配送线路设计问题的基本思想和原理如下：(1)编码我们使用自然数编码，即序数编码。货物运输路线可以编成长度为N+m的染色体其中表示某一辆车配送某个点的货物，m表示完成任务所需的最小车辆数。(2)产生初始群体初始群体随机产生，即产生个货物运输任务点的排列，如，如果 ，且，将s至的数向后移动一位，将0插入第s位，然后继续上述操作，直到m个0全部插入为止。这样就构成了一条初始染色体。用这种方法构造一个群体的染色体。如：983721546，该编码插零之后变成0983072105460。这代表需要三辆车进行配送工作。第1辆车行走路线为09830，即从仓库出发到依次到9、8、3
7、超市再回到配送中心。第2辆车行走路线为07210，第3辆车行走路线为05460。(3)适应度函数适应度函数取，其中为染色体的适应度，为常数，为初始种群中最好的染色体的运输成本，为染色体对应的运输成本。(4)遗传算子选取最佳保留的轮盘赌复制法进行染色体的复制。变异算子采用反转变异。交叉算子用最大保留交叉，其操作过程为： 若染色体交叉点处的两个基因都为0，则直接进行顺序交叉运算； 若染色体交叉点处的基因不全为0，则将交叉点左移（右移），直到左右两个交叉处的基因都为0，再进行顺序交叉运算。(5)算法的实现步骤步骤1：采用自然数编码的方式，构造表示可行车路线的染色体；步骤2：设置控制参数，包括交叉率、
8、变异率、群体规模n=20；步骤3：初始化，令，随机产生初始群体，群体中包括个染色体，每个染色体代表一条行车线路；步骤4：令；步骤5：将群体中的第个染色体译为线路长度；步骤6：计算适应度；步骤7：若满足算法终止条件，则停止，否则继续；步骤8：；步骤9：若，回到步骤5，否则，转步骤11；步骤11：进行最大保留交叉、基于位的变异和倒位操作；步骤12: ；步骤13：若满足算法终止条件，则停止，否则转步骤4。2 数学模型2.1 符号定义与说明表2-1 符号定义与说明表：一量运货车的最大容量：该配送中心服务的客户总数: 派送费用最小时所需的车辆数：第i位客户所需货物：车k由i驶向j：k车完成点i的配送任务
9、：第i位客户最早允许接货时间：第i位客户最晚允许接货时间：车辆在第i位客户处等待时间:车辆在第i位客户处迟到时间：车辆到达第i位客户处时间：从第i第j位客户所需行车时间：第i位客户处装货(或卸货)所需时间：第i位客户与第j位客户之间的距离：车辆行驶单位距离的运输成本：车辆早到单位时间产生的等待损失：车辆迟到单位时间应承担的惩罚：派送货物产生的总损失：总运输成本：所有车辆早到产生总的等待损失：所有车辆迟到所受的总惩罚：所有车量人员的固定成本：每派出一辆车的固定费用：车辆平均行驶速度2.2 主要问题一个物流配送中心，有一定数量载重量为Q的车辆，需要对N个客户进行货物配送工作，客户i的货物需求量为
10、，且 Q，车辆必须在一定的时间范围内到达，早于到达将产生等待损失，迟于到达将处以一定的迟到惩罚。因此，我们需要解决如下问题：客户总数N，每辆车的容量Q(吨/辆)，各项任务的货运量(单位：吨)，装货(或卸货)时间(单位：小时)以及要求每项任务开始执行的时间范围，假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为公里/小时，我们需要解决的问题是如何安排车辆的行驶线路使总运行所产生的费用最少，路程最短，并且尽量及时送到货物。2.3 数学模型的建立2.3.1 车辆数量的确定设配送中心需要向N个客户送货，每个客户的货物需求量是(i1，2，N)，每辆配送车的载重量是，且。首先为了安排路线需要对要使用的
11、车辆数有一个估计。在现实情况中，货物装(卸)车越复杂，约束条件越多，一辆车的实际载货量就越小。确定需要的车辆数： 符号“ ”表示取整数，为参数，01。约束条件越多，货物装(卸)越复杂，值越小。取为0.8。2.3.2. 引入01变量(1)表示车辆是否从客户行驶到客户。定义其为01变量，则有 (2)表示客户的任务由车辆完成。同样定义其为01变量，则有 2.3.3 目标函数的确定题目要求所选配送线路产生的总费用最小，我们确定总费用为目标函数，记为。总费用由运输成本A、固定成本D、等待损失B和迟到惩罚C组成，根据题意有： 所以，总费用Z最小化为： 2.3.4 约束条件的确定约束1：车辆的运送总重量应不
12、超过车辆的最大载重，即车辆有一定的运送能力，则可引入约束条件： () (1)约束2：每个客户只能由一辆车来配送，则可引入约束条件： (2) 2.3.5 变量之间关系的确定确定等待时间，超时时间为： (3) (4)车辆从客户(或配送中心)到客户(或配送中心)需经过两段时间为： (5)设车辆为客户运送完货物后即为客户运送，则到达客户处时间和到达客户处时间之间的关系为： (6) 2.3.6 此数学规划模型为： (1) (2) (3) (4) (5) (6)3 应用研究南京宁果公司是以水果配送为主要业务的一家物流类型企业，而配送线路的设计直接影响到企业的成本以及顾客服务体验。然而宁果在这方面做的不够理
13、想，物流配送成本居高不下，送货不够及时都是存在的严峻问题。以江苏省南京市雨花台区凤集大道，经纬度=(31.9388， 118.6510)的点为坐标原点(0，0)。以此为基准，建立一个二维直角坐标系。计算出来的坐标是一个相对坐标，具体配送中心和苏果超市的的坐标： 图3-1 基于电子地图的坐标系图从而得到新的坐标如下表：表3-1 宁果公司客户坐标值表 编号X坐标Y坐标编号X坐标Y坐标022.3675 5.1700 1118.2648 4.1362 114.3509 10.5990 1227.3027 11.4210 213.8016 9.9296 1320.7024 2.3305 316.5482 10.5117 1428.0151 11.3265 413.0291 13.7414 1512.7308 7.2772 512.4755 11.6575 1615.6877 7.5374 612.8489 12.7158 1718.6768 10.4826 710.4370 14.5268 1816.6683 11.1664 812.3682 10.9409 1915.7928 16.0102
