求解复杂有时间窗装卸货问题的遗传算法

Genetic algorithm for solving the complex pickup and delivery problem with time windows

有时间窗装卸货问题是为一个车队安排最优的服务路径以满足客户的运输需求,每个客户的装卸货任务由一辆车完成,即在该客户的装货点装载一定数量的货物后运往该客户的卸货点,所有任务的完成必须满足车辆的容量约束、行程约束和客户装卸货点的时间窗约束。从多车库、多货物类型和满载三个方面对一般有时间窗装卸问题(PDPTW)进行了扩展,提出一种解决复杂PDPTW问题的遗传算法,实验结果表明,该算法能有效解决复杂PDPTW问题,并取得较好的优化结果。

The pickup and delivery problem with time windows requires that a group of vehicles satisfy a collection of customer requests. Each customer request requires the use of a single vehicle both to load a specified amount of goods at one location and to deliver them to another location. All requests must be performed without violating either ttle vehicle maximal capacity constrain, maximal travel distance limitation or the customer time window stipulated at each location. The general PDPTW was extended on three aspects, which were multi depots, multi load type and fully loaded. And a genetic algorithm suitable for solving complex PDPTW was proposed. As the experiment proved, when this algorithm is used for solving complex PDPTW, it can obtain preferable result and solve this problem effeetivcly.