Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation
Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation
复制标题
DOI：
10.1016/j.ejor.2005.12.029
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
K. Tan;C. Cheong;C. Goh
中科院分区：
文献类型：
--
作者：
K. Tan;C. Cheong;C. Goh
本文考虑了有限容量的车辆从一个中央仓库到一组地理上分散的客户，只有当车辆到达客户的实际需求被揭示的路由。随机需求车辆路径问题（VRPSD）的解决方案涉及到在时间窗和车辆容量等约束条件下，以最小行驶距离、驾驶员报酬和车辆数量为目标，对完整的路径计划进行优化。为了解决这样一个多目标和多模态的组合优化问题，本文提出了一种多目标进化算法，结合两个VRPSD特定的局部开发和路线模拟方法来评估解决方案的适应度。提出了一种新的方法来评估解决方案的质量VRPSD的顶部比较他们的预期成本。结果表明，该算法是能够找到有用的折衷解决方案的VRPSD和解决方案是强大的随机性质的问题。最后，以所罗门的带时间窗车辆路径问题（VRPTW）为例，对算法进行了验证。
This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.