期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 83, 期 -, 页码 111-122出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2015.02.005
关键词
Parallel simulated annealing; Simultaneous delivery and pickup; Vehicle routing; Time windows
资金
- State Key Program of National Natural Science of China [71132008]
- General Program of National Natural Science of China [71473013]
- China Scholarship Council [201207090034]
- Fundamental Research Funds for the Central Universities of China [2012YJS034]
This paper addresses a variant of the vehicle routing problem in which customers require simultaneous pickup and delivery of goods during specific individual time windows (VRPSPDTW). A general mixed integer programming model is employed to minimize the routing cost due to: the cost of vehicles and the travel cost of vehicles. A parallel Simulated Annealing (p-SA) algorithm that includes a Residual Capacity and Radial Surcharge (CRS) insertion-based heuristic is developed and applied to solve this NP-hard optimization problem. Computational results are reported for 65 test problems from Wang and Chen's benchmark and compared with the results from a Genetic Algorithm (GA) that minimizes the number of vehicles (NV) as the primary objective. Experimental results demonstrate the effectiveness of the p-SA algorithm, which is able to achieve the same objective response as 100% of the Wang and Chen small-scale benchmarks (number of customers from 10 to 50). For the Wang and Chen medium-scale benchmarks (number of 100 customers), the p-SA algorithm obtains better NV solutions for 12 instances and the same NV solutions for the remaining 44 instances. For the 44 instances with the same NV solutions, a secondary objective, travel distance (TD), the p-SA provides better solutions than the GA for 16 instances, and equal solutions for 7 instances. In addition, solutions are found for 30 large-scale instances, with customers of 200, 400, 600, 800 and 1000, which may serve as a new benchmark for the VRPSPDTW problem. (C) 2015 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据