VRP first appeared in a paper by George Dantzig and John Ramser (1959), in which first algorithmic approach …show more content…
n) are available and loads qj are required to be delivered to points Pj (j= 1... M) from a depot Po. Given the distances d, between all such points it is required to minimize the total distance covered by the trucks. For convenience of computation Ci are ordered such that Ci-1 < Ci (I = 2…n) and it is assumed that Ci<<∑qj (j = 1…m) Since in the solution some trucks may only be partially loaded, xi needs to be sufficiently large to ensure that all loads are allocated. For purposes of computation it is therefore made infinite. It might be noted that if Cn≥ ∑qj (j = 1…m) then the problem becomes the traveling salesman problem. The Dantzig and Ramser method focuses only on the state C2= C3= ... Cn = 0 Due to the restriction that, in the first of N stages, only customers whose combined load does not exceed C1/2N-1 are permitted to be linked, points may be linked that are far apart, and may be virtually on opposite ends of a straight line through the depot. Although obviously long links may be excluded in the initial stages by 'rapid corrections,' when two points become linked in an 'aggregation' they remain aggregated. As a result, this method tends to lay more emphasis on filling trucks to near capacity than on minimizing distance. The distance table in the Nth stage could require each cell to contain the shortest distance from the depot through 2N points, i.e., the 'traveling salesman …show more content…
Each customer is serviced exactly once and, furthermore, all the customers must be assigned to vehicles without exceeding vehicle capacities (Bodin et al. 1983). In the vehicle routing and scheduling problem with time window constraints (VRSPTW), these issues must be addressed under the added complexity of allowable delivery times, or time windows, stemming from the fact that some customers impose delivery deadlines and earliest-delivery-time constraint. In the presence of time windows, the total routing and scheduling costs include not only the total travel distance and time costs considered for routing problems, but also the cost of waiting time incurred when a vehicle arrives too early at a customer location or when the vehicle is loaded or unloaded. The VRSPTW has emerged as an important area for progress in handling realistic complications and generalizations of the basic routing model (Schrage 1981, Bodin et al.). Time windows arise naturally in problems faced by business organizations that work on fixed time schedules. Specific examples include bank deliveries, postal deliveries, industrial refuse col- lection, dial-a-ride service, and school bus routing and scheduling. So far, this type of constraint has been handled in an ad hoc manner, mostly by