下载文档原格式
基于模糊时间窗的车辆调度问题研究王旭坪;张凯;胡祥培【摘要】An increasing number of enterprises are focusing on the vehicle routing problems (VRP) because of expanded logistics support. VRP belongs to typical NP-Hard problems. An enterprise typically spends 25% to 30% of total expenses on vehicle routing problems because they can affect economic efficiency and customer benefits. Therefore, it is important to research VRP and optimize logistics activities.Exiting literature has focused on the vehicle routing problem with hard time and soft time windows. In the VRP with hard time window, the service time must fall within each customer' s time window. Due to the limitation of hard time window and the number of available vehicles, it is often unable to find feasible schedules. To deal with issues pertaining to the violation of time window, researchers have proposed the concept of "soft time window". In the VRP with soft time window, a penalty cost is added once a time window is violated, and the penalty cost is often assumed to be linear with the degree of violation. In some cases, violation of time window does not directly incur any penalty cost, although the satisfaction levels of customers may drop and lead to benefit loss in the long term. In many realistic applications, the hard time window or soft time window does represent customer requirements very well. Under these circumstances, the fuzzy processing of time window can reflect customers' requirements well and truly. Until now, few studies have addressed VRP-with fuzzy timewindow when the number of vehicle is limited. There are many real-life situations where the number of vehicle is limited, such as logistics distribution, post express and so on. Thus, this paper proposes and solves vehicle routing problems based on the fuzzy time window and a definite number of vehicles. In this paper, a fuzzy membership function is used to characterize customers' satisfaction levels by analyzing customers' practical requirements of the service time window.A multi-objective model with two goals is formatted. The objective considered here is to maximize customers' service level and minimize the total cost. In the model, customers' satisfaction is quantified as the fuzzy membership function of starting service time and time window based on fuzzy processing. To solve the multi-objective model, a genetic algorithm that can optimize fuzzy information is developed. The algorithm adopts an improved chromosome representation based on customer requirements, which can obtain the optimal number of vehicles automatically. Compared with other chromosome representation, our approach can maximize the number of customers to be serviced. A new handling constraint method based on genetic algorithm is designed. The method can help avoid the difficulty of incorporating the penalty factor into penalty strategy and simplify the handling of constraints. Another benefit is to solve the situation that not enough vehicles are available to service all customers and the value of customer sequence number is limited. More importantly, a fuzzy optimization procedure is applied to decide the optimal starting service time for each customer.Our experimental results demonstrate that theefficiency of our proposed model and algorithm in solving vehicle routing problems and maintaining an acceptable customer satisfaction level. Moreover, the proposed model can also optimize vehicle routing problems with the hard time window by setting parameters of all customers' satisfaction level as 1.%基于现实生活中配送企业车辆责源有限和顾客对服务时间要求并非完全刚性的特征,通过时间窗模糊化处理将顾客服务的满意度量化为配送服务开始时间的模糊隶属度函数.在一定满意度下,构建了基于模糊时间窗的车辆调度模型,根据模型的特点,改进了基于客户的染色体编码方式,设定了一种新的约束处理方法,避免了惩罚策略中选取惩罚因子的困难.在算法中用模糊优化程序处理问题的模糊特征,通过对顾客服务时间的局部调整来确定最佳服务时间.最终通过实例验证与原结果比较发现,引用模糊时间窗函数不仅可以降低配送成本,而且有利于节省运力资源.【期刊名称】《管理工程学报》【年(卷),期】2011(025)003【总页数】7页(P148-154)【关键词】模糊时间窗;车辆调度;多目标优化;混合遗传算法;顾客满意度【作者】王旭坪;张凯;胡祥培【作者单位】大连理工大学系统工程研究所,辽宁大连116023;大连理工大学系统工程研究所,辽宁大连116023;大连理工大学系统工程研究所,辽宁大连116023【正文语种】中文【中图分类】TP18车辆调度问题是典型的组合优化问题，属于NP-Hard难题，其在邮政投递、物流配送和交通运输系统等领域都有着重要的应用。
带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。
根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。
然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。
模型一（见5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。
模型一的求解采用遗传算法（见5.1.3），对题目给出的实际问题进行求解，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。
模型一的思路清晰，考虑条件全面。
但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。
模型二的想法比较合理，易于实施，但还有待改进。
关键词：规划 时间窗 物流 车辆路径 遗传算法一、 问题重述一个中心仓库，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为i q ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。
并具体求解以下算例：客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量i q （单位：吨）、装货（或卸货）时间i s （单位：小时）以及要求每项任务开始执行的时间范围[],i i a b 由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短； （2）进一步请讨论当客户i 的货物需求量i q 为随机参数时的数学模型及处理方法。
带时间窗车辆路径问题的最优解带时间窗的车辆调度问题是物流配送系统的关键之关键，对它的研究越来越重视。
本文将建立物流管理中的带时间窗车辆路径问题的模型，并得到此模型的最优解，有一定的实用意义。
标签：带时间窗车辆路径问题物流管理组合优化一、提出问题在许多物流配送系统中，管理者需要采取有效的配送策略以提高服务水平、降低货运费用。
其中车辆路径问题是亟待解决的一个重要问题，此问题可描述如下：有一个货物需求点（或称顾客），已知每个需求点的需求量及地理位置，至多用K辆汽车从中心仓库（或配送中心）到达这批需求点，每辆汽车载重量一定，安排汽车路线使运输距离最短并且满足每条线路不超过汽车载重量和每个需求点的需求量且必须只能用一辆汽车来满足。
带时间窗车辆路径问题（VRPTW，vehicle routing problem with time windows）是在车辆路径问题中加入了客户要求访问的时间窗口，由于在现实生活中许多问题都可以归结为VRPTW来处理，但处理的好坏将直接影响到一个企业的效益和顾客的服务质量，所以对它的研究越来越受到人们的重视，目前对它的求解主要集中在启发式算法上。
20世纪90年代后，遗传算法、禁忌搜索算法、模拟退火算法、人工神经网络算法和动态蚁群算法等启发式算法的出现，为求解VRPTW提供了新的工具。
但是，遗传算法存在“早熟性收敛”问题，禁忌搜索算法、人工神经网络算法也存在一些不尽人意的地方，如何针对VRPTW的特点，构造简单、寻优性能优异的启发式算法，这不仅对于物流配送系统而且对于许多可转化为VRPTW求解的优化组合问题均具有十分重要的意义。
实际数据表明动态蚁群算法行之有效，不失为一种求解VRPTW的性能优越的启发式算法。
二、问题描述VRPTW可以描述如下：给定车辆集合V，需求点集合C和有向图G。
此有向图有|C|+2个顶点，顶点1,2,K,n表示需求点，顶点0表示离开时的中心仓库，顶点n+1表示返回时的中心仓库，把顶点0,1,2,3,K,n+1记作集合N。
摘要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。
在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。
带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。
本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。
并对所采用的遗传算法的基本理论做了论述。
对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。
经实验分析，取得了较好的结果。
由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。
关键词：物流配送车辆优化调度遗传算法时间窗AbstractRecent years, logistics, taken as "third profit resource”, has been developing rapidly. In the developed commercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had brought forth, then the conception of Time Window has come into being. The vehicle-scheduling problem with time window is also a NP-hard problem being more complicated than VSP.This text has been researched to the vehicle-scheduling problem with time window on the basis of researched to logistic vehicle scheduling problem. And it has explained the basic theory of genetic algorithm.On the VSP with time window, while the restraints of capacity and time windows are changed into object restraints, a mathematic model is established. We use technique such as maximum preserved crossover and design genetic algorithm on nature number, which can deal with soft time windows through experimental analysis, have made better result. Because this problem was studied together for group members, this text has expounded the part about fitness function and mutation operator that I finished.Key words:logistic distribution vehicle scheduling problem genetic algorithm time windows目录摘要 (I)Abstract (II)目录......................................................................................................... I II 引言.. (1)第1章概述 (2)1.1研究背景 (2)1.2物流配送车辆优化调度的研究动态和水平 (4)1.2.1 问题的提出 (4)1.2.2 分类 (5)1.2.3 基本问题与基本方法 (6)1.2.4 算法 (6)1.2.5 货运车辆优化调度问题的分类 (8)1.3 研究的意义 (9)1.4 研究的范围 (10)第2章有时间窗的车辆优化调度问题(VSPTW) (11)2.1 时间窗的定义 (11)2.2 VSPTW问题的结构 (13)第3章遗传算法基本理论 (14)3.1 遗传算法的基本原理 (14)3.1.1 遗传算法的特点 (14)3.1.2 遗传算法的基本步骤和处理流程 (15)3.1.3 遗传算法的应用 (16)3.2 编码 (17)3.2.1二进制编码 (18)3.2.2Gray编码 (18)3.2.3实数向量编码 (18)3.2.4排列编码 (19)3.3 适应度函数 (19)3.3.1 目标函数映射成适应度函数 (19)3.3.2 适应度定标 (20)3.4 遗传算法的基因操作 (21)3.4.1 选择算子 (21)3.4.2 交叉算子 (22)3.4.3 变异算子 (25)3.5 遗传算法控制参数设定 (28)第4章遗传算法求解有时间窗非满载VSP (30)4.1 问题描述 (30)4.2 数学模型 (31)4.2.1 一般VSP模型 (31)4.2.2 有时间窗VSP模型 (32)4.3 算法设计 (33)4.3.1 算法流程图 (33)4.3.2 染色体结构 (33)4.3.3 约束处理 (35)4.3.4 适应度函数 (36)4.3.5 初始种群 (36)4.3.6 遗传算子 (36)4.3.7 控制参数和终止条件 (37)4.4 算法实现 (39)4.5 实验及结果分析 (39)4.5.1控制参数选定 (39)4.5.2实例实验 (43)4.5.3实例数据 (44)4.5.4实例数据分析 (44)结论 (45)参考文献 (47)谢辞 (48)引言随着市场经济的发展，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。
物流配送路径规划中的时间窗问题研究与应用摘要：在物流配送系统中，时间窗问题是一个重要的研究方向。
时间窗指的是物流配送过程中，每个客户对送货时间的限定。
在进行路径规划时，必须考虑到这些时间窗的限制，以确保配送的准时和高效。
本文将探讨时间窗问题的研究背景、定义、分类以及应用，并讨论相关研究的最新进展和未来发展方向。
1. 引言物流配送是现代经济运作中不可或缺的一环，它涉及到从供应商到客户的商品运输。
为了确保商品能够按时送达，保证供应链的顺利运作，物流配送路径规划成为一个十分复杂的问题。
在实际配送中，客户的送货时间限制成为了一项不可忽视的因素。
因此，研究如何在配送过程中合理安排时间窗成为了一项重要的课题。
2. 时间窗问题的定义与分类时间窗问题是指在物流配送过程中，每个客户对送货时间的限定问题。
通常来说，每个送货点都会对送货的时间窗进行要求，以确保送货的合理性和高效性。
时间窗问题可以分为硬性时间窗和软性时间窗。
硬性时间窗是指送货时间窗必须严格遵守，若送货晚于时间窗，则被视为违约，不符合客户的需求。
软性时间窗则允许在一定范围内有所延迟，但延迟时间越长，对配送成本和客户满意度的影响也越大。
3. 时间窗问题的应用研究时间窗问题在物流配送领域有着广泛的应用研究。
主要包括以下几个方面：3.1 路径规划优化时间窗问题的一个重要应用是在路径规划中进行优化。
通过考虑送货点的时间窗限制，并采用合适的算法和模型，可以在尽量减少配送成本的同时保证配送的准时性。
研究者提出了多种求解算法，例如遗传算法、模拟退火算法等，并结合实际场景进行验证和优化。
3.2 送货路线调整在实际配送过程中，由于各种原因（道路拥堵、天气等），送货路线需要进行调整。
时间窗问题可以帮助配送员进行及时调整，选择最优的路线以保证送货的准时性。
3.3 仓库和配送中心的布局规划仓库和配送中心的布局规划也需要考虑时间窗的因素。
通过合理规划仓库和配送中心的位置，可以减少配送距离和时间，提高配送效率，降低成本。
带时间窗的车辆路径问题（VRPTW）是一种重要的组合优化问题，在许多实际的物流配送领域都有着广泛的应用。
该问题是对经典的车辆路径问题（VRP）进行了进一步扩展，考虑了车辆在每个节点进行配送时的时间窗约束。
VRPTW的数学建模和求解具有一定的复杂性，需要综合考虑车辆的路径规划和时间限制方面的因素。
本文将对带时间窗的车辆路径问题进行数学建模，并探讨一些常见的求解方法和算法。
一、问题描述带时间窗的车辆路径问题是一个典型的组合优化问题，通常可以描述为：给定一个具有时间窗约束的有向图G=(V,E)，其中V表示配送点（包括仓库和客户），E表示路径集合，以及每个节点v∈V都有一个配送需求q(v)，以及一个时间窗[Tmin(v),Tmax(v)]，表示了可以在节点v进行配送的时间范围；另外，给定有限数量的车辆，每辆车的容量有限，且其行驶速度相同。
问题的目标是设计一组最优的车辆路径，使得所有的配送需求都能够在其对应的时间窗内得到满足，且最小化车辆的行驶距离、行驶时间或总成本，从而降低配送成本和提高配送效率。
二、数学建模针对带时间窗的车辆路径问题，一般可以采用整数规划（IP）模型来进行数学建模。
以下是一个经典的整数规划模型：1. 定义决策变量：设xij为车辆在节点i和节点j之间的路径是否被选中，若被选中则为1，否则为0；di表示节点i的配送需求量；t表示车辆到达每个节点的时间；C表示车辆的行驶成本。
2. 目标函数：目标是最小化车辆的行驶成本，可以表示为：minimize C = ∑(i,j)∈E cij*xij其中cij表示路径(i,j)的单位成本。
3. 约束条件：（1）容量约束：车辆在途中的配送总量不能超过其容量限制。
∑j∈V di*xij ≤ Q, for i∈V（2）时间窗约束：Tmin(v) ≤ t ≤ Tmax(v), for v∈Vtij = t + di + dij, for (i,j)∈E, i≠0, j≠0（3）路径连通约束：∑i∈V,x0i=1; ∑j∈V,xji=1, for j∈V（4）路径闭合约束：∑i∈V xi0 = ∑i∈V xi0 = k其中k表示车辆数量。
