Vehicle Routing problem
Outline
Vehicle Routing Problem Problem Statement Ant Colony Optimization Technique Genetic algorithm
Vehicle Routing Problem
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles
The Problem is of Economic Importance to Businesses because of Time and cost associated with fleet of Delivery Vehicles to transport products.
specializations of the vehicle routing problem exist
Vehicle Routing Problem with Pickup and Delivery(VRPPD). Vehicle Routing Problem with Time Windows (VRPTW). Capacitated Vehicle Routing Problem (with or without Time Windows.
Problem Statement
The basic Vehicle Routing Problem (VRP): Minimize total distance travelled subject to
depot
each customer is serviced each route starts and ends at the capacity restrictions on the vehicles
Problem Statement
Parameter Objective Fleet Size Domain Minimizing the time/distance, for no of vehicles 1 Vehicle and Multiple Vehicle Single Depot and Multiple Imposed/not imposed
Fleet Type No of Depots Total time /distance Constraints Time Windows Vehicle Capacity
Imposed/not imposed Finite /Infinite
Ant Colony Optimization(ACO)
ACO approach to find the solution for vehicle routing problem. ACO is meta-Heuristic technique that uses the Artificial ants to find solutions combinatorial optimization problem. ACO simulates the behavior of ant colonies as they finding the food with most efficient routes from their nests to the sources.
Purpose Of ACO Algo
A) Route Construction
Using Aco, Individual ant simulates a vehicle, and route is constructed by incrementally selecting Customers until all the customers have been visited.
ACO alog is used, each ant must construct a vehicle route that visits each customer.
B) Trail Updating
The pheromone trails of the ants must be updated to reflect the ants performance and quality of the solution found.
C) Multiple Ant colonies
It used for solving the problem for the VRP might be more effective.
Genetic Algorithm
The purpose is to determine a set of routes which serve many people quickly and without using too many transfers. Problem specific crossover and mutation operators are devised. 1) Transit Routing 2) Transit Scheduling
Transit Routing: Result
0 1 2 8
5 14 7 6
11 9 10 12 13
Description for single Vehicle Routing
A B C D E A-B-C-H-G-D-E-F-I-J-K-A A-B-C-D-E-F-H-G-I-J-K-A A-B-C-D-E-F-H-G-K-J-I-A A-B-C-D-E-F-G-K-J-H-I-A F G D E I H K A I H K
B C
F G
Transit Scheduling
Given the fleet size, the idea is to determine the schedule such that the total time spent waiting () by transferring and nontransferring passengers is minimized. We schedule the passengers and non transferring passengers according to route .
Thank you
