Design of multiple-vehicle delivery tours satisfying time constraints

The authors studied the following organization for the letter and parcel pick-up and delivery problem in an urban environment: the working day is divided in time periods during which each vehicle starts from a sorting center, travels to a precise area of the region, picks up and delivers letters and parcels, and then returns to the depot to have the collected material sorted out for delivery during the following period. The intent of this approach is to have each zone serviced by one vehicle only to facilitate the work of the dispatcher and the routing of each vehicle. The authors have developed a method of partitioning an urban region into zones so as to minimize the total number of vehicles used or the total distance traveled by all the vehicles. The first part of the method determines the zones and the average number of points to visit. Then, a first refinement of the method takes into account the daily variability of the demand in each zone, and a second refinement examines the advantage of allowing some overlapping of zones for the purpose of having an overloaded vehicle relieved by one from an adjacent zone.