英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
一种带硬时间窗和同时取送货的车辆路径问题
的启发式算法
摘 要
本文主要是对车辆路径问题中一种特殊情况——带硬时间窗和同时取送货的车辆路径问题（VRPSPDHTW）进行讨论。车辆路线问题的目标通常是获取最小化旅行距离或旅行成本。通过查阅文献我们可以看出，在时间窗车辆路径问题中总是定义相同的目标表函数，但是在时间窗车辆路径问题中，由时间窗引起的等待问题不能被忽略。因此本文中，目标函数被指定为VRPSPDHTW中等待的最小化，数学模型被定义为一个集合，提出启发式算法来解决这一问题，同是对所罗门数据集进行修改以适应问题的结构和测试提出的算法。
关键词：车辆路线问题，接送服务，时间窗
1.绪论
与仓库和最终用户之间货物配送有关的问题被称为车辆路径问题（VRP），车辆路线问题在物流配送中普遍存在，一般的VRP包括一个分配问题，一个旅行商问题和一个车辆路径问题。Dantzig和Ramser在1959年首次提出VRP问题，描述了其在现实中的应用并提出第一个数学规划模型以及解决问题的方法。
基本的VRP问题包括一个中央仓库，一组需要从仓库运送货物的客户以及一个位于仓库中的相同车辆，VRP问题的目标是最大限度地减少总旅行距离，旅行费用或是用于服务所有客户的车辆数量，在组合优化领域VRP被认为是NP-hard。在已有的文献中，有几类VRP问题的研究，它们都是基本VRP的扩展，[4]和[5]给出了VRP及其变体的细节和文献。
客户要求在指定时间窗内交货的VRP的子类被称为带时间窗约束的车辆路径问题（VRPTW）[6]，时间窗口表征服务应该包含从最早（ai）到最晚（bi）的允许时间。同时允许车辆比ai到达更早到达客户i，但是在这种情况下它将一直等到服务在ai时间开始。如果发生迟到——即在bi之后到达则是不允许的，考虑这种类型的时间窗的问题被称为具有硬时间窗（VRPHTW）的车辆路线问题。另一方面，时间窗口的下限和上限可以被违反，这类问题被称为具有软时间窗的车辆路线问题（VRPSTW）[7]。另外，任何路线（旅行时间 服务时间）的总持续时间不能超过预定的路线持续时间。Salversberg证明了VRPTW是一个NP问题[8]，VRPTW的典型应用包括银行递送，校车路线，邮递[9]-[11]，VRPTW的早期工作通常以案例研究为导向[12]-[14]。后来，研究人员将注意力集中在开发有效的最优方法和设计启发式解决实际大小问题上，有关VRP和VRPTW的详细研究包括[10][11][15][16]。
基本VRP的扩展是拾取和交付（VRPPD）的车辆路线问题，在VRPPD中，每个客户都有两种类型的需求，例如提货需求（pi）和交货需求（di）。交货需求是指从仓库运输到客户的货物量;提货需求是指从客户运送到仓库的货物量，考虑到处理交货和需求方面的问题，VRPPD问题被分为以下3类：
首先交付第二个VRPPD：客户不止一次被访问。
首先，货物从仓库运输到客户，然后，从客户到仓库，交货和提货客户之间有优先权。
混合皮卡和交付VRPPD：交货和取件之间没有优先权。
交货需求和提货需求以混合顺序进行服务，客户不止一次访问。
同时取货和交货VRPPD：交货和取件需求同时提供服务。
这类问题具体表示为VRPSPD，客户只能被访问一次。
VRPSPD问题在现实生活中经常遇到，例如在软饮料行业中，满瓶的饮料从仓库运输到市场，空瓶被送回仓库；杂货行业的货物从仓库流向市场，而过期的产品流入仓库。VRPSPD是NP-hard组合优化问题，因为它是VRP问题的一种类型。 Min介绍了VRPSPD问题，并提出了一个图书馆之间运输图书的算法，其中有一个车站，2辆车和22个顾客，该算法是基于集群第一路由第二种方法；Dethloff提出这个问题的数学公式，并且开发了一个基于插入的启发式来解决这个问题；Ropke和Pisinger开发了一个统一的模型，能够处理来自文献[24]的大多数变体问题；Bianchess和Righini提出并比较构造算法、本地搜索和禁忌搜索算法的性能；Tang Montane提出一种数学公式和禁忌搜索算法，该算法通过使用VRPSPD的频率惩罚方案来加强和多样化；Zachariadis等人提出基于禁忌搜索和引导局部搜索的混合元启发式方法；Gajpal和Abad提出了VRPSPD的蚁群系统算法；Ai和Kachitvchyanukul提出VRPSPD问题的数学公式和粒子群算法，该公式是Min，Dethloff和Tang Montane等人提出的数学公式的推广；Chen等人提出基于记录的混合元启发式方法来记录旅行禁忌表和路线改进例程； Zachariadis等人提出适用于VRPSPD问题的自适应记忆编程方法；Angellini和Mansini为VRPSPDTW开发了一个分支和价格算法；Mingyong和Erbao（2010）提出了一种改进的差分进化算法（IDE）来解决VRPSPDTW问题，与Angellini和Mingyong的工作不同，在这项研究中，确定问题的目标是最小化同时拾取和难度窗口以及arp目标函数等待，指定了数学模型并开发了解决方案的启发式算法。
2.问题的描述和表示
我们提出一种数学公式并为VRPSPDHTW开发了启发式算法，提出的问题是NP难题，因为它是VRPSPD和VRPTW的扩展，所提出的数学模型是基于Dethloff的数学模型，并在其中插入了时间窗，其目标函数被认为是总等待时间的最小化。
VRPSPDHTW问题可以正式定义如下：设G=（V,A）是一个图，其中V={v0,v1,hellip;vn}是一个顶点集，而A={（vi,vj）:vi,vjisin;V，ine;j}是一个弧集，顶点v0代表仓库，顶点vi代表客户，其中i=1...n，每个客户都有一个非负的提货数量pi，交货数量为di，服务时间为si，每辆车的容量为Q。VRPSPDHTW的目标是确定一组满足以下要求的路线：
1）每条路线在仓库开始和结束；
2）每一位顾客只需一辆车就能得到一次服务；
3）在相关的时间间隔内，所有的客户交付和取件需求都完全满足（车辆被允许早于ai到达客户到达，但不允许晚于bi到达）；
4）通过任何路线的车辆总负载不超过车辆容量Q；
5）仓库中存在均匀的车队；
6）总等待时间最小化。
在模型中使用的符号和参数给出如下：
J：所有客户位置的集合；
J0：所有节点的集合，即客户地点和仓库；
V：所有车辆的集合；
C：车辆容量；
tij：节点之间的旅行时间；
si：服务时间；
Zij：在节点之间添加服务时间和旅行时间（Zij = si tij）；
Wiv：车辆在节点i的服务开始时间v；
Viv：车辆到达节点i的时间v；
Dj：客户j的交货金额；
N：节点数量；
Pj：提取客户的金额；
M：很多；
ai：节点i处服务的最早开始时间；
bi：节点i的最新服务开始时间；
决策变量：
Lv#39;：车辆v在离开仓库时的加载；
Lj：服务客户j后车辆v的负载；
pi;j：用于禁止子巡视的变量；
Xijv=二进制变量，指示车辆v从节点i直接到达节点j（xijv=1）的位置（xijv=0）。
（1）
（2）
（3）
（4）
； （5）
（6）
（7）and ； （8）
； （9）
； （10）
； （11）
； （12）
； （13）
； （14）
； （15）
； （16）
（17）
；； （18）
在模型中，目标函数（1）是最小化节点之间的等待时间；约束条件（2）表示每个客户节点必须仅服务一次；约束条件（3）表明每个客户必须使用同一车辆服务；约束条件（4）给出初始车辆载荷；约束条件（5）是第一个客户之后的车辆载荷；约束条件（6）是车辆载荷途中；约束条件（7）和（8）比较第一个客户和途中后的车辆载荷和车辆容量；约束（9）是子巡视中断约束；约束（10）通过路由和约束确定所有节点的服务开始时间；约束（11）确保服务的开始时间在时间间隔之间；约束（12）和（13）分别确定通过路线到达任何节点的到达时间，以及到达仓库后第一个节点的到达时间；约束（14）确定仓库后第一个节点的服务开始时间；约束（15）确保服务将在车辆到达节点后开始；约束（16）确定等待时间；约束（17）和（18）描述了决策变量的领域；pi;j是非负变量，而xijv是二元变量。
3. VRPSPDHTW的启发式
由于使用上面提出的数学模型解决了测试问题的结果，很明显确定这种方法不能在合理的时间内为较大尺寸的测试问题产生好的结果。为了解决更大的问题，本文提出了一种启发式方法，启发式的逐步流程如下所示：
1）打开节点列表L并通过增加服务ai的最早开始时间值来对它们排序，如果多个节点具有相同的ai，则通过增加服务bi的最近开始时间值来对它们进行排序；
2）选取列表L上的顶层节点i，并将其放在列表K的底部，然后从列表L中删除节点i并计算I0和Iq：
（19）
3）计算列表K中节点的RD和RP值，其中RD（q）代表剩余输送能力，RP（q）代表库中的剩余提货能力；
（20）
（21）
4）确认列表L中的节点的下列公式得到满足；
and （22）
如果满意，这意味着节点u可以放置在节点i之后。如果不是，则节点u不能放置在节点i之后，这意味着它不可行；
5）如果L#39;=Ǿ关闭列表K，则将满足步骤4的节点放置在列表L#39;处并返回步骤2；
6）计算列表L#39;处节点的Wik和Vj k值（Vjk，车辆k到达节点j的时间; Fik，车辆k到节点i的出发时间）；
and （23）
如果对于列表L#39;中的所有节点Vikgt; bi，则关闭列表K，返回到步骤2；
7）计算等待时间为：
（24）
8）如果Fnk tn0gt; b0（这意味着返回仓库的时间大于仓库服务的最近开始时间），这是不可行的。如果列表K#39;上的所有节点均满足此条件，则返回步骤2；
9）选择列表K中Wiand最小的节点，从列表L中删除节点，返回步骤2；
10）如果列表L为空，停止算法。
为了调查这里提出的数学模型[31]和启发式算法[32]的性能，解决了5,7,10,15和20个客户的测试问题，选择这些问题的主要想法是，对于有更多客户的测试问题，数学模型不能在合理的时间段内产生最佳解决方案，在本研究中这被认为是7200秒。所罗门的原始测试问题包括每个案例中的100个客户，满足我们的情况下的约束，并且车辆的总容量被确定为其原始值的一半。
4.数值案例
由于VRR_SPD_HTW以前从未解决，因此在文献中没有数据可用于测试VRRSPDHTW，因此我们应该对所罗门的数据进行修改以便在算法中使用，Solomon的问题的完整描述可以在Solomon中找到[10]。所罗门的问题分为三类：C，R和RC。 每个类别都有8到12个例子，每个示例都有一个仓库和100个客户，每个类别分为两类，分别为类型1和类型2，类型1问题和类型2问题之间的差异是车辆容量和时间窗口。类型1问题的时间窗口狭窄，车辆容量小，而类型2问题的时间窗口宽，车辆容量大。 客户的位置均匀分布在R1和R2中，并集中在C1和C2中。 对于组RC1和RC2，聚类和随机分布是混合的。
我们使用Salhi和Nagy的公式[20]来修改所罗门的数据，为了调查数学模型和启发式的有效性，生成了5,7,10,15和20个客户的测试问题，所罗门的原始测试问题包括每个案例中的100个客户，并且为了满足约束条件，车辆的总容量被确定为其原始值的一半，该数学模型使用具有2.6Ghz且低于1Gb Ram的微处理器的个人计算机，使用
全文共11570字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16540]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
