"AN MILP FRAMEWORK FOR DYNAMIC VEHICLE ROUTING"

DONDO, RODOLFO G.; CERDA, JAIME

LATIN AMERICAN APPLIED RESEARCH

Universidad Nacional del Sur

Lugar: Buenos Aires; Año: 2006 vol. 36 p. 255 - 261

0327-0793

A key issue in logistics is the efficient management of a vehicle fleet servicing a set of customers with known demands. Every vehicle route must start and finish at the assigned depot, each customer is to be visited by a single vehicle and vehicle capacities must not be exceeded. These are the constraints for the capacitated vehicle routing problem (VRP) whose objective is usually the minimization of the travel distance. When every customer has an associated time window, we are dealing with the vehicle routing problem with time windows (VRPTW), an NP-hard problem extensively studied. In the static VPRTW, all the problem data are given. A more challenging subject is the dynamic VRPTW (DRVPTW) where routes must be periodically updated because of new service requests. In DVRPTW, the information on the problem is time-dependent since the data are in part given a priori and in part dynamically updated. As a result, the best solution must be periodically revised. There are two classes of DVRPTW solution methodologies: the immediate assignment that updates vehicle routes as soon as a new service request is received, and the deferred assignment retaining the new service calls for a certain time period before dispatching them all at once. The latter type has been adopted in this paper. At the time of revising their routes, the vehicles are already on duty and some nodes have already been visited. The remaining old customers that have designated vehicles are either being serviced or awaiting service. The customers to be considered in the DVRPTW include not only old customers still to be serviced but also new visit requests. The DVRPTW is tackled by solving a series of static VRPTW problems, with each one being defined every time the input data is updated. The approach assumes that each vehicle will start its new route at the location where it is servicing or to which it is traveling. with known demands. Every vehicle route must start and finish at the assigned depot, each customer is to be visited by a single vehicle and vehicle capacities must not be exceeded. These are the constraints for the capacitated vehicle routing problem (VRP) whose objective is usually the minimization of the travel distance. When every customer has an associated time window, we are dealing with the vehicle routing problem with time windows (VRPTW), an NP-hard problem extensively studied. In the static VPRTW, all the problem data are given. A more challenging subject is the dynamic VRPTW (DRVPTW) where routes must be periodically updated because of new service requests. In DVRPTW, the information on the problem is time-dependent since the data are in part given a priori and in part dynamically updated. As a result, the best solution must be periodically revised. There are two classes of DVRPTW solution methodologies: the immediate assignment that updates vehicle routes as soon as a new service request is received, and the deferred assignment retaining the new service calls for a certain time period before dispatching them all at once. The latter type has been adopted in this paper. At the time of revising their routes, the vehicles are already on duty and some nodes have already been visited. The remaining old customers that have designated vehicles are either being serviced or awaiting service. The customers to be considered in the DVRPTW include not only old customers still to be serviced but also new visit requests. The DVRPTW is tackled by solving a series of static VRPTW problems, with each one being defined every time the input data is updated. The approach assumes that each vehicle will start its new route at the location where it is servicing or to which it is traveling. A key issue in logistics is the efficient management of a vehicle fleet servicing a set of customers with known demands. Every vehicle route must start and finish at the assigned depot, each customer is to be visited by a single vehicle and vehicle capacities must not be exceeded. These are the constraints for the capacitated vehicle routing problem (VRP) whose objective is usually the minimization of the travel distance. When every customer has an associated time window, we are dealing with the vehicle routing problem with time windows (VRPTW), an NP-hard problem extensively studied. In the static VPRTW, all the problem data are given. A more challenging subject is the dynamic VRPTW (DRVPTW) where routes must be periodically updated because of new service requests. In DVRPTW, the information on the problem is time-dependent since the data are in part given a priori and in part dynamically updated. As a result, the best solution must be periodically revised. There are two classes of DVRPTW solution methodologies: the immediate assignment that updates vehicle routes as soon as a new service request is received, and the deferred assignment retaining the new service calls for a certain time period before dispatching them all at once. The latter type has been adopted in this paper. At the time of revising their routes, the vehicles are already on duty and some nodes have already been visited. The remaining old customers that have designated vehicles are either being serviced or awaiting service. The customers to be considered in the DVRPTW include not only old customers still to be serviced but also new visit requests. The DVRPTW is tackled by solving a series of static VRPTW problems, with each one being defined every time the input data is updated. The approach assumes that each vehicle will start its new route at the location where it is servicing or to which it is traveling.