Open Access Open Access  Restricted Access Subscription Access

Methods of Capacitated Vehicle Routing Problem based on Constraints


Affiliations
1 Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India
 

The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" In our paper to describe the Methods of Capacitated Vehicle Routing Problem we implement using c code the Clarke and Wright's savings algorithm to solve our problem where the constraints are to find a solution which minimizes the total transportation costs, demand and capacity of a vehicle. Furthermore, the solution must satisfy the restrictions that every customer is visited exactly once, where the demanded quantities are delivered, and the total demand on every route must be within the vehicle's capacity. The transportation costs are specified as the cost of driving from any city to any other city. The costs are identical in the two directions between two given points. We use this above methodology in solving both Single and Multi depot vehicle routing problem and compare their results.

Keywords

C&W, CVRP, MD, SD, TSP, VRP.
User
Notifications
Font Size

  • Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964; 12:568–81.

  • Dantzig GB, Ramser JH. The truck dispatching problem (PDF). Management Science. 1959 Oct; 6(1):80–91. DOI: 10.1287/mnsc.6.1.80.

  • The vehicle routing problem. Philadelphia: Soc for Industrial and Applied Mathematics; 2002. ISBN: 0-89871-579-2. |first1= missing |last1= in Authors list (help)

  • Hasle G, Lie K-A, Quak E, Kloster O. Geometric modeling, numerical simulation, and optimization applied mathematics at SINTEF. Berlin: Springer Verlag; 2007. ISBN: 978-3-540-68783-2.

  • Comtois C, Slack B, Rodrigue J-P. The geography of transport systems. 3rd ed. London: Routledge, Taylor and Francis Group; 2013. ISBN: 978-0-415-82254-1.

  • Beck JC, Prosser P, Selensky E. Vehicle routing and job shop scheduling: What’s the difference (PDF). Proceedings of the 13th International Conference on Artificial Intelligence Planning and Scheduling; 2003.

  • Miller CE, Tucker EW, Zemlin RA. Integer programming formulations and travelling salesman problems. J ACM. 1960; 7(4):326–9. DOI:10.1145/321043.321046.

  • Christofides N, Mingozzi A, Toth P. The vehicle routing problem. Chichester, UK: Wiley; 1979. p. 315–38.

  • Jun L, Yaohuang G. Dispatch optimize theory and methods for logistic distribution vehicle. Beijing: Chinese Commodity Publish House; 2001.

  • Hoong CL, Melvyn S, Kwong MT. Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research. 2003; 148:559–69.

  • Shiquan Z, Guoguang H. Vehicle scheduling problem with single depot in complex conditions. Systems Engineering. 2005; 23:29–32.

  • Hongmei C, Li G, Yaxin H. Hybrid algorithm for solving variable fleet vehicle routing problem. Journal of Wuhan University of Technology. 2009; 33:647–50.


Abstract Views: 777

PDF Views: 471




  • Methods of Capacitated Vehicle Routing Problem based on Constraints

Abstract Views: 777  |  PDF Views: 471

Authors

Susikh Dhara
Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India
Shrena Sarkar
Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India
Shalini Roy
Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India
Deepika Mandal
Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India
Harinandan Tunga
Department of Computer Science and Engineering, RCC Institute of Information and Technology, Kolkata - 700015, West Bengal, India

Abstract


The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" In our paper to describe the Methods of Capacitated Vehicle Routing Problem we implement using c code the Clarke and Wright's savings algorithm to solve our problem where the constraints are to find a solution which minimizes the total transportation costs, demand and capacity of a vehicle. Furthermore, the solution must satisfy the restrictions that every customer is visited exactly once, where the demanded quantities are delivered, and the total demand on every route must be within the vehicle's capacity. The transportation costs are specified as the cost of driving from any city to any other city. The costs are identical in the two directions between two given points. We use this above methodology in solving both Single and Multi depot vehicle routing problem and compare their results.

Keywords


C&W, CVRP, MD, SD, TSP, VRP.

References