VRPTW中的多目标遗传算法：距离与车辆数优化

5星 · 超过95%的资源需积分: 31 115 浏览量更新于2024-07-27 2 收藏 1.71MB PDF 举报

本文主要探讨了多目标优化遗传算法在解决带有时间窗的车辆路线问题（Vehicle Routing Problem with Time Windows, VRPTW）中的应用。VRPTW是一个经典的组合优化问题，它涉及到如何有效地调度一组拥有有限载货能力的车辆，从一个中心仓库出发，去满足分布在不同地理位置、需求已知且有预定义时间窗口的客户群体。目标是优化车辆的行驶路径，既要满足所有约束条件，如时间限制和载货容量，又要最小化旅行距离和所需的车辆数量。多目标优化关注的是寻找多个优化目标之间的平衡点，而非单一最优解。遗传算法是一种启发式搜索方法，模仿自然选择和遗传机制，在大量可能的解决方案中通过迭代进行进化，逐渐逼近潜在的全局最优解。在本文中，作者提出了一种混合的多目标遗传算法，旨在同时优化两个关键目标：总行驶距离和所需车辆数目。该算法的工作流程可能包括以下步骤： 1. 初始化种群：创建一组随机生成的车辆路线方案作为初始种群。 2. 适应度评估：对每个方案计算其对应的旅行距离和车辆数，形成适应度函数值。 3. 选择：根据适应度值选择一部分个体进入下一代，通常使用非支配排序和轮盘赌选择策略。 4. 变异与交叉：通过变异（改变个体的部分特征）和交叉（交换个体部分路线）操作产生新的个体。 5. 重复步骤2-4：不断迭代，直到达到一定的终止条件（如最大迭代次数或适应度值收敛）。论文作者Tan、Chew和Lee在2006年的《Computational Optimization and Applications》上发表了他们的研究成果，该研究对于理解和改进VRPTW的求解策略具有重要意义，因为它提供了一个实用的工具，有助于在实际应用中平衡运输效率和资源利用，特别是在物流和配送等领域。此外，文章还提供了详细的算法设计和实验结果，这对于其他研究者来说，是进一步探索多目标优化算法在类似问题上的扩展和改进的重要参考依据。

HYBRID MULTIOBJECTIVE EVOLUTIONARY ALGORITHM FOR SVRPTW 121

2.2. The Solomon’s 56 benchmark problems for VRPTW

The six benchmark problems [84] designed speciﬁcally for the vehicle routing problem

with time window constraints (VRPTW) are adopted in this paper to illustrate the

performance of the HMOEA. The Solomon’s problems consist of 56 data sets, which

have been extensively used for benchmarking different heuristics in literature over the

years. The problems vary in ﬂeet size, vehicle capacity, traveling time of vehicles, spatial

and temporal distribution of customers. In addition to that, the time windows allocated

for every customer and the percentage of customers with tight time-windows constraint

also vary for different test cases. The customers’ details are given in the sequence of

customer index, location in x and y coordinates, the demand for load, the ready time, due

date and the service time required. All the test problems consist of 100 customers, which

are generally adopted as the problem size for performance comparisons in VRPTW. The

traveling time between customers is equal to the corresponding Euclidean distance. The

56 problems are divided into 6 categories based on the pattern of customers’ locations

and time windows. These 6 categories are named as C

, C

, R

, RC

and RC

The problem category R has all customers located remotely and the problem category

C refers to clustered type of customers. RC is a category of problems having a mixture of

remote and clustered customers. The geographical distribution determines the traveling

distances between customers [33]. In the cluster type of distribution, customers’ loca-

tions are closer to each other and thus the traveling distances are shorter. In the remote

type of distribution, customers’ locations are remotely placed. Therefore the traveling

distance is relatively longer in the R category as compared to the C category problems.

Generally, the C category problems are easier to be solved because their solutions are

less sensitive to the usually small distances among customers. In contrast, the R category

problems require more efforts to obtain a correct sequence of customers in each route,

and different sequences may result in large differences in terms of the routing cost.

The data sets are further categorized according to the time windows constraints.

The problems in category 1, e.g., C

, R

, RC

, generally come with a smaller time

window, and the problems in category 2, e.g., C

, R

and RC

are often allocated

with a longer time window. In the problem sets of R

and RC

, the time windows are

generated randomly. In the problem set of C

, however, the variations of time windows

are small. A shorter time window indicates that many candidate solutions can become

infeasible easily after reproduction due to the tight constraint. In contrast, a larger time

window means that more feasible solutions are possible and subsequently encourages

the existence of longer routes, i.e., each vehicle can serve a larger number of customers.

In ﬁgure 3,thex-y coordinate depicts the distribution of customers’ locations for the six

different categories, C

, C

, R

, RC

and RC

. Figures 3(a), (c) and (e) are labeled

with “cluster” or/and “remote” to show the distribution of customers corresponding

to its problem category. For example, in ﬁgure 3(e), there are two types of customer

distribution patterns, i.e., cluster and remote, since the RC category consists of both the

R and C type problems.

3. A hybrid multiobjective evolutionary algorithm

As described in the Introduction, the VRPTW can be best solved by means of multi-

objective optimization, i.e., it involves optimizing routes for multiple vehicles to meet

剩余36页未读，继续阅读

zjutfp

粉丝: 1
资源: 2

VRPTW中的多目标遗传算法：距离与车辆数优化

多目标遗传算法工具箱

多目标遗传算法优化案例

多目标优化遗传算法实现

基于遗传算法的配电网多目标优化

HIV-TB合并感染的滑模控制与多目标遗传算法优化治疗模型

多目标优化问题与遗传算法的结合探讨

遗传算法中的多目标优化问题处理

遗传算法与多目标优化问题的应对策略

多目标优化 遗传算法

多目标优化遗传算法研究现状

最新资源

多目标优化遗传算法