英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
带时间窗约束的多车辆集配货问题的遗传算法
摘要：本文提出了一种带时间窗约束的多车辆集货和配送问题的遗传算法（m-PDPTW）。m-PDPTW是一种优化车辆路径问题，它必须满足供应商与客户之间优先级约束、车辆载货量约束和时间约束的要求。本文简要回顾了它的PDPTW，提出了一种基于遗传算法和Pareto优势方法的求解方法，给出了一组满足m-PDPTW的解决方案，使总的运输费用、总的等待时间和总车辆数最小化。
一、介绍
现在，货物的运输问题在日益发展的现代社会经济中占据了非常重要的位置。在时间和经济约束对货物运输问题的影响下，它的决策变得非常困难，并需要使用来自许多不同学科（制造业、信息技术、组合优化等）的工具辅助。实际上，运输系统和运输日程安排的过程也因为它们之间的关系动态的性质和它们运行的多重性导致的庞大规模变得越来越复杂并难以处理。
现在已经有许多科学研究在针对解决车辆路径问题（VRP）展开。VRP是一种满足旅行需求的车辆路径优化问题。其他的一些研究人员对VRP的一种重要变体产生了浓厚的兴趣，即带有车辆容量限制的PDPTW（带有时间窗约束的集货和配货问题）。
PDPTW一般可以被分为两种：1-PDPTW（单车辆）和m-PDPTW（多车辆）。
我们的目标是设计一种基于遗传算法的m-pdptw决策工具，Pareto优势法为解决这一问题提供了一套令人满意的能够使总成本、总等待时间和总车辆数最小化的解决方案。
文献综述
2.1车辆路径问题
车辆路径问题（VRP）是一种多目标组合优化问题，在很多文献中都有很多的研究和变形。它属于NP-hard问题。[Christofides.N and al., 1979][ Lenstra.J and al., 1981]
启发式算法也同样被应用于求解车辆路径问题。在这些方法中，我们可以应用Montamenni.R 等人对DVRP决策的蚁群算法。[Montamenni. R and al., 2002]
VRP可以被定义为如下：给定一个仓库D和一组客户订单建立一个运输网络，仓库拥有的货车车辆数是已知的，所有的车辆都是从这个仓库出发并在完成任务后回到这个仓库。在这些运输线路中，一个客户能且仅能被一辆车辆服务一次，并且货车的载货量不能够超过运输过程中的车辆最大载货量限制。[Nabaa.M and al., 2007]
Savelsbergh 等人已经证明了VRP是一个NP-hard问题[Savelsbergh.M.P. and al., 1995]。而m-PDPTW是VRP的延伸，这是一个NP-hard问题。。
2.2 PDPTW:带有时间窗约束的集货和配送问题。
PDPTW是VRPTW的一种变体，它除了存在时间限制外，这个问题还意味着存在一组客户和一组地理位置上的供应商。每个线路还必须满足优先级约束，以确保在访问供应商之前不会先访问客户。 [Psaraftis.H.n., 1983]
Psaraftis,H.N 开发了一种动态方法来解决1-PDP的问题，他将目标函数作为总运输时间和非客户满意度最小化的权重求解。[Psaraftis.H.n., 1980]
Jih, W 等人已经开发了一种基于混合遗传算法的方法来解决1-PDPTW，目标是将总成本和总等待时间的组合最小化。[Jih. w and al. 1999]
另一种遗传算法由Velasco, N 等人开发，用以解决1-PDP双目标问题，即在满足最紧急要求的优先级时，总运输时间必须达到最小化。在这篇文献中，提出的解决这个问题的方法是基于带精英策略的非支配排序的遗传算法（nsga-ii）。[Velasco. N and al.2006]
Kammarti,R 等人解决了1- PDPTW。利用特殊遗传算子的进化算法，尽量减少总的运输距离、总的等待时间和总的延误时间之间的折中，提供了一套可行的方法。[Kammarti.r and al 2004][Kammarti R and al 2005a]
这项工作已经被扩展，提出了一种基于使用下界和Pareto优势方法的新方法，以最小化总运输距离和总迟到时间之间的妥协。[Kammarti. R and al 2006][Kammarti R and al 2007]
关于m-PDPTW，Sol, M 等人提出了一个分支与价格切割算法来解决m-PDPTW，使满足所有旅行需求的车辆数量和总运输距离最小化。[Sol. M and al.1994]
Quan, L等人基于集成原则提出了一种基于目标函数的构造启发式算法，将总成本最小化，包括车辆的固定成本和可选择的旅行距离的差旅费。[Quan. L and al., 2003]
Li, H等人提出了一种新的基于tabu算法的元启发式方法，用于求解m-PDPTW。[Li. H and al., 2001]
Li, H 等人已经开发了一个“Squeaky wheel”方法来解决m- PDPTW的局部搜索。[Li. h and al 2002]
一种遗传算法是由Harbaoui Dridi,I等人开发的，用于处理m-PDPTW，使运输距离和总运输成本最小化。[Harbaoui Dridi I and al.2008]
三、数学公式
我们提出的问题有以下几项参数：
：一组表示客户、供应商和仓库的点；
：一组表示一组客户和供应商的点；
：一组表示供应商的点；
：一组表示顾客的点；
：车辆编号；
：顶点i和顶点j之间的欧几里得距离。如果，那么ij之间的线路不存在；
：车辆k从顶点i出发到达顶点j所使用的时间；
：顶点i的时间窗口；
：顶点i的结束时间
：顶点i需要的货物数量。如果，顶点i是供应商；如果，顶点i是客户；如果，则顶点i已经被服务过；
：车辆k的载重量；
：前顶点索引；
：后顶点索引；
：车辆编码索引；
；
：车辆到达顶点i的时间；
：车辆从顶点i出发的时间；
：车辆k访问顶点i的货物数量；
：车辆k的运输成本
一个顶点只能被服务一次；货车的载货量不能超过其最大载货量限制；车场是车辆的起点和终点；车辆在每个顶点停留一段时间来满足各点的需求；如果车辆到达顶点i时在它的时间窗口开始时间之前，那么车辆等待。
该目标最小化函数为以下内容：
（1）
（2）
（3）
（4）
（5）
（6）
（7）
（8）
（9）
（10）
（11）
（12）
（13）
（14）
约束条件（2）和（3）确保每个顶点只被单个车辆访问一次；约束条件条件（4）和（5）确定车辆路径开始和结束是仓库；约束（6）保证了车辆的路径连续性；约束条件（7）、（8）和（9）是容量约束；优先级约束由条件（10）和（11）保证；约束条件（12）（13）和（14）确保了车辆集配货遵守时间窗口约束。
四、多标准评价
一个多目标问题被定义为一个优化向量问题，它寻求优化向量函数成本的几个组成部分。
4.1帕雷托支配方法
一个多标准的问题P包括变量N、不等式约束M、等式约束P和标准K，它们的表述如下。
（15）
因此，找到解决办法，在标准之间达成可能的妥协是很有必要的。经济学家诉帕累托提出的帕累托最优概念经常被使用。[Pareto. V.,1897]
如果在解决方案空间中任何其他点都占主导地位，那么解决方案就是帕累托最优。这些点被指出是非主流的解决方案。
一个点支配。如果
图1给出了一个我们试图最小化f1和f2的例子。点1、3和5不是以点2为主导的，点3以点3为主，点4以点5为主。
通过使用上面给出的参数，我们建议优化方程（1）所给出的函数。在前面提到的约束条件（2）hellip;（14）下，考虑到我们将f最小化，它认为sol1占主导地位。如果etet。也有人认为，两个解决方案不是一个比另一个占主导地位，如果他们检查一个条件跟随系统：
m-pdptw多标准优化的遗传算法
5.1解决方案编码。
染色体是一个继承（排列）顶点，它表示一个工具访问所有顶点的顺序。图2表示染色体形式下的解。
5.2初始人口的产生
初始种群的选择是很重要的，因为它可以使遗传算法或多或少地收敛到全局最优。
在我们的案例下，我们将产生两种种群。根据排列列表编码（图2），第一个填充标记为，表示所有节点与所有车辆一起访问（图2）。第二组注意到的表示每个车辆访问的节点数。已知K在1和之间变化。图3显示了一个的的例子。
考虑到图2所示的人口数量，如图3所示的纠正程序和人口数量，我们在图4中显示了的人口数量。
5.3交叉操作
在最初的群体产生之后，我们将进入交叉阶段，这将确保重新组合父母的基因来培养新的后代。我们选择一点交叉。
5.4变异操作
变异算子的目的是随机选择两个位置，即染色体上的位置，并交换它们各自的值。
5.5纠正程序
纠正优先级和容量的原则[Harbaoui Dridi.I and al., 2008]是确保客户在尊重车辆容量的同时，不会在供应商面前出现。
建议将运输费用、总等候时间和车辆总数尽量减少
一个例子如图3所示，在人口的生成之后，我们确定每个人，f1、f2和f3值，对应车辆号、总等待时间和总运输费用。我们得到了后来的人口。图5显示了这一人群的个体样本。
我们已将此结果复制到人口的每个个体，以获得其后的人口。之后，我们根据较低的f1、f2和f3的值来选择总体，直到获得所有非主流的解决方案。下面表示方法的算法。
步骤一：创建一个初始种群（n）；
步骤二：用个体的交叉、变异或拷贝填充中间人群（2n）；
步骤三：优先级的修正程序；
步骤四：创建两个中间人口（ 2n*2n）表示每个车辆的路由。而生成的数字还没有达到；
步骤五：确定每个人的适应度值，以获得其后的人口；
步骤六：按健康的最小值（车辆总等候时间/总运输费用）计算人口；
步骤七：复制非主导解决方案生成的生成数。
我们给出了确定不同人口的程序。[Harbaoui dridi, I and al 2008]
七、计算结果
下表（表1）表示我们的问题的参数。
实验结果见表2。
总等待时间是用时间单位表示的，我们的方法提供了一组非主导的解决方案，以确保选择的灵活性。这组解决方案为制造商将根据其决定采取的Pareto空间。
八、结论
在这篇论文中，我们提出了一种基于帕累托控制法的方法来解决m-PDPTW的遗传方法。
在第一部分中，我们对VRP、1-PDPTW和m-PDPTW进行了简要的文献综述。我们的问题的数学公式在第二部分中进行了详细的说明。然后详细描述了用帕累托支配法来确定一组非受控的解决方案，将我们的目标函数最小化。
集配一体化的车辆路径问题的蚁群系统（Acs）
摘要：本文采用蚁群算法（ACS）算法，解决了一种组合优化问题，即集配一体化（vrpsdp）的车辆路径问题。ACS是一种算法的方法，它的灵感来源于真正的蚂蚁的觅食行为。用人工蚂蚁来解决问题的方法是利用从先前生成的解决方案中使用信息素的方法来解决这个问题，这个算法利用了一个建筑规则以及两个多路径的本地搜索方案
该算法还可以解决回程和混合负载（VRPBM）的车辆路径问题。对文献中可用的基准问题实例进行了广泛的数值实验。结果表明，与现有的算法相比，acs具有较好的效果。
一、介绍
传统的供应链管理主要集中在材料的正向流动上。然而，新的环境法规和对退货和再利用产品的激励措施，增加了近年来供应链的逆向流动。对材料逆向流动的管理需要在供应链管理中开辟出一个新的领域，称为逆向物流。逆向物流试图通过重新获得在供应链中丢失或未充分利用的价值来产生额外的收益，而逆向物流的一个问题是，车辆规划者和调度员需要考虑从一个客户的单个车辆运送和取货。同时交付和拾取的车辆路径问题（VRPSDP）的特点是:在该地区的地理位置上使用一组相同的车辆，这些车辆位于仓库中，用于服务客户。每辆车的容量均为Q。客户要求在车辆的单次访问过程中交付给定的运输货物。目标是设计一套最低成本的路线，为所有客户提供服务，以使车辆上的载荷低于车辆在该路线中每一点的Q值。VRPSDP是一个NP-hard问题，因为当我们将所有的接收需求或所有的交付需求都设置为零时，问题就会降低到一个已知的NP-hard问题（CVRP）的容量化车辆路径问题。VRPSDP与反向运输（VRPB）的车辆路径问题密切相关，该问题要求在从回
全文共6660字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16295]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
