Multi-Depot Vehicle Routing Problem with Time Windows and Multi-Type Vehicle Number Limits and its Genetic Algorithm
Multi-Depot Vehicle Routing Problem with Time Windows and Multi-Type Vehicle Number Limits and its Genetic Algorithm
复制标题
DOI：
10.1109/wicom.2008.1502
复制
发表时间：
2008-11
期刊：
影响因子：
--
通讯作者：
Xuping Wang;Chuanlei Xu;Hongyan Shang
中科院分区：
文献类型：
--
作者：
Xuping Wang;Chuanlei Xu;Hongyan Shang
针对现代大型企业建设多仓库、多类型车辆数量有限的情况，给出了车辆数量有限、车辆种类限制有限的多仓库车辆带时间窗路径问题。建立了上述问题的数学模型，该模型反映了多车型限制和车辆数量限制的特点，与MDVRPTW兼容。提出了一种基于客户的改进的染色体表示方法，可以表示车辆段、路径和未服务的客户。构造了该问题的遗传算法和种群初始化算法。设计了一种新的基于遗传算法的操纵约束方法，避免了惩罚策略中惩罚因子选择的困难，简化了操纵约束。实验证明了该算法在上述条件下对MDVRPTW的有效性。
According to the situation that modern large enterprise builds multiple depots and multi-type vehicles with the limited number are in the depots, multi-depot vehicle routing problem with time windows (MDVRPTW) where limited number of vehicles and multi-type vehicle limits is given. Mathematical model of the above problem is constructed, which reflects the feature of the multi-type vehicle limit and the limited number of vehicles, compatible with MDVRPTW. An improved chromosome representation is proposed on the basis of customer, which can denote the vehicle sent by depot, path and the customer unserviced. The genetic algorithm for the problem and the population initialization algorithm are constructed. A new handling constraint method based on genetic algorithm is designed, avoiding the difficulty of selecting the penalty factor in penalty strategy and making the handling constrain simplify. The validity of the algorithm to MDVRPTW with the above- mentioned conditions is proved by the experiments.