A multi-trip, multi-depot vehicle routing problem with vehicle time windows constraints.

The Vehicle Routing Problem (VRP) consists of the routing of capacitated vehicles over a network of customers with specific demands, beginning and ending at a central depot. The objective is to design a set of vehicle routes minimizing travel cost incurred in servicing the customers. Existing models on the optimal routing of vehicles have not considered imposition of vehicle time windows. This feature is present in practice, coming in the form of crew shifting and government regulations regarding the use of heavy vehicles. Another feature of this study is the possibility of having more than one trip in a period. This study also considers the cost of not utilizing all the vehicles, other studies considered the non-utilization of vehicles but did not consider the cost of the idle vehicles. Another important factor considered in this study is the presence of the maintenance depot. A vehicle that has reached its mileage limit should visit the maintenance depot, constant upkeep of vehicles would lessen the probability of vehicle breakdowns. The model formulation utilized mixed integer linear programming. It consists of one objective function that aims to minimize the total cost incurred by the system. Validation was done using actual data for customer demand, service time, and customer weights taken from the Solid Waste Department of the Las Piñas City Government. The General Algebraic Modeling System (GAMS) was used to validate the model. Sensitivity analysis was done by changing a certain parameter, for the values related to the vehicle time windows, maintenance policy, number and capacity of vehicles, and growth rate, and holding other values constant. This was done through graphical analysis and the 2K design of experiments tool. The program devised for this study is the VRPVTW version 1 software. It was developed using Visual Basic 6.0. It utilizes Microsoft Excel and Notepad for data inputs and the GAMS software for solving the problem. The study exhibited that the presence of the maintenance depot increased the total cost incurred by the system. As for vehicle time windows and number of vehicles, extreme levels also yield a high cost. As for the vehicle capacity, a higher level is more desirable since it has the capability of servicing more customers, therefore satisfying more demand. Among three parameters-vehicle capacity, number of vehicles, and growth rate-it was found out that the number of vehicles contributes the highest effect to the total cost of the system. But a combination of a high number of vehicles with high capacities yields the most desirable effect of lower cost. This effect, however, is only applicable up to a certain limit, as idle cost increases with more vehicles at hand