Vehicle routing with a sparse feasibility graph |
| |
Institution: | 1. Laboratory for Manufacturing Systems and Automation, Department of Mechanical Engineering and Aeronautics, University of Patras, Patras 26504, Greece;1. Department of Applied Science and Humanities, Shaheed Bhagat Singh State Technical Campus, Ferozepur, Punjab, India;2. Research scholar, I.K. Gujral Punjab Technical University, Kapurthala, Punjab, India;3. Department of Applied Sciences, Lala Lajpat Rai Institute of Engineering and Technology, Moga, Punjab, India |
| |
Abstract: | In this paper we introduce the concept of a feasibility graph for vehicle routing problems, a graph where two customers are linked if and only if it is possible for them to be successive (adjacent) customers on some feasible vehicle route. We consider the problem of designing vehicle routes when the underlying feasibility graph is sparse, i.e. when any customer has only a few other customers to which they can be adjacent on a vehicle route. This problem arose during a consultancy study that involved the design of fixed vehicle routes delivering to contiguous (adjacent) postal districts. A heuristic algorithm for the problem is presented and computational results given for a number of test problems involving up to 856 customers. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|