Solving vehicle routing problem using multi agent technology

Abstract

In today’s world transportation plays an important role in logistics and it appears in various sections of logistics processes. It occupies one-third of the amount in the logistics costs and influence the performance of logistics system hugely. Therefore through better transportation planning businesses can improve their customer experience (service level) and reduce the overall logistic cost. Companies are using people to do this task manually. When number of destinations and number of transport vehicles are high, route planner has to find lots of information (information about roads, distance between destinations, traffic condition of roads, etc.…) and synthesize them manually to find the solution. Therefore this task is became very time consuming and produces inefficient solutions most of the time. Because of these factors, it requires lots of human intervention and wasting lot of time and money because of in-efficient route designs. This research studies how multi agent technology can be used to overcome the above identified issue. Existing automated solutions for vehicle routing problem like Tabu search (TS), genetic algorithm (GA), and evolutionary algorithms (EA) uses destination point and vehicle details as data points, but with multi agent technology these data points convert to agents who can negotiate and take decisions collaboratively. Because it has features like autonomy, negotiation and emergent property, it introduces autonomy to the system and comes up with best or near best solutions as emergent properties through negotiations. As the subject of this study 8.00 pm transport planning of MillenniumIT Software (Pvt) Ltd was chose and process of planning routes is automated using multi agent technology. 8.00 pm transport requests are different for each day. Therefore route plan should change day by day to cater the requirement. As a solution operation team of MillenniumIT generates manual route plans for each day and it is a challenging task because of the high number of passengers and vehicle are increasing the complexity of the problem. In automated system it used information about vehicles (number of vehicles, capacity of each vehicle) and passengers (passenger name, latitude of destination. longitude of destination) as inputs. After the requesting process is over system generates agents for each passenger and vehicle. Then those agents are developing a solution as an emergent property through negotiation and as output it generates route plans for 8.00 pm transportation of given day. iv Then shuttle request data for 10 days were selected randomly as sample dataset to evaluate the automated solution. Then manually generated and automated shuttle plans for those shuttle requests were collected, calculated the total route distance and compared against each other. The results show that 8 times out of 10 automated route plan is cost effective than the manually generated plan. Therefore it was concluded that Vehicle routing problem can solve by multi agent technology.