考虑软时间窗的同时送取货随机旅行时间车辆路径问题

Stochastic Travel-time Vehicle Routing Problem with Simultaneous Pick-up and Delivery Considering Soft Time Windows

摘要:

考虑车辆总旅行时间约束和车辆载重限制以及客户对服务时间窗的要求，研究带有软时间窗的同时送取货随机旅行时间车辆路径问题（STT?VRPSPD），建立机会约束规划模型。将禁忌搜索算法与分散搜索算法相结合，构建混合分散禁忌搜索（HSTS）算法，并采用C?W节约算法生成初始解。基于经典的Dethloff算例和Solomon时间窗生成方法，分别生成包括50个客户、200个客户各20组算例，算例测试结果验证了混合分散禁忌搜索算法的有效性。

Abstract:

According to the constraints of the total vehicle travel time， vehicle load， and the soft time windows， we studied the stochastic travel-time vehicle routing problem with simultaneous pick-up and delivery （STT-VRPSPD） considering soft time windows and established a chance-constrained programming model. Combining the tabu search algorithm with the scatter search algorithm， a hybrid scatter tabu search （HSTS） algorithm was constructed， and the C-W saving algorithm was used to generate initial solutions. Based on the classic Dethloff instances and Solomon time window generation method， 20 groups of instances including 50 customers and 20 groups of instances including 200 customers were generated respectively for numerical tests. The numerical results verify the effectiveness of the HSTS algorithm.