Method, system and program for creating a delivery plan

• US 20030078802A1
• Filed: 10/07/2002
• Published: 04/24/2003
• Est. Priority Date: 10/22/2001
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yonezawa, Takashi
• Application Number:
  US10/265,754
• Publication Number:
  US 20030078802A1
• Time in Patent Office: Days
• US Class Current: 705/1
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/08355 Routing methods

Abstract

Where a plurality of delivery vehicles must start at a product distribution center, deliver products to one or more destinations on a route and then return the distribution center, a delivery plan is used to minimize operating costs. Possible delivery plans, having a plurality of delivery routes, are established. Plan evaluation values are established by accumulating the travel times for each route in the plan. The travel time for each route is the sum of the actual inter-destination travel times and weighted travel times for the initial (distribution center to first destination) and final (last destination to distribution center) segments of the route. The weighting reduces the effect of the initial and final segments relative to the effect of the inter-destination travel times. The evaluation values are compared in a series of iterations until it is determined that no further improvement can be obtained in evaluation value.

Claims

1. For use in a computer system including a processor and a memory, a method for creating a delivery plan including delivery routes for each of a plurality of delivery vehicles, each route starting at a distribution center, including one or more sequential delivery destinations and end with a return to the distribution center, a computer-implemented method comprising the steps of:

(1) generating a tentative delivery plan using data of delivery instances stored in the memory;

(2) calculating an evaluation value for the tentative delivery plan;

(3) executing an operation that alters the topology of the tentative delivery plan to generate a new delivery plan;

(4) calculating an evaluation value for the new delivery plan;

(5) comparing the evaluation value of the tentative delivery plan to the evaluation value of the new delivery plan;

(6) where the evaluation value of the new delivery plan is superior, substituting the new delivery plan for the tentative delivery plan; and

(7) causing the processor to output the selected delivery plan,

wherein the evaluation value for a delivery plan is based on the accumulated delivery times for the delivery routes included in the plan, and

each of the steps (2) and (4) of calculating the evaluation values further including the steps of, for each route in the delivery plan,

establishing a first travel time from the distribution center to the first destination on the route,

modifying the established travel time by a coefficient k₁ to calculate a first value,

establishing a second travel time from the last destination to the distribution center for,

modifying a second travel time by a coefficient k₂ to calculate a second value, and

using the modified travel times and the actual inter-destination delivery times in calculating the evaluation value for each route in the delivery.

2. The method as defined in claim 1 further including the steps of reiterating steps (1) through (6) until it is determined that no further improvements in evaluation values are obtained.

3. The method as defined in claim 2 wherein each of the coefficients k₁ and k₂ has a value between 0 and 1 and the steps of modifying the first and second travel times are performed by modifying the established travel time by the coefficient associated with that travel time.

4. A computer system for creating a delivery plan that includes one or more delivery routes, each route being traveled by a delivery vehicle that starts at a distribution center, makes a delivery to one or more destinations and returns to the distribution center, the computer system comprising:

(1) logic for generating a tentative delivery plan using stored data of a delivery instance;

(2) logic for calculating an evaluation value for the tentative delivery plan;

(3) logic for modifying the topology of the tentative delivery plan to generate a new delivery plan;

(4) logic for calculating an evaluation value of the new delivery plan;

(5) comparison logic for comparing the evaluation value of the tentative delivery plan to that of the new delivery plan;

(6) control for substituting the new delivery plan for the tentative delivery plan when the comparison logic indicates the evaluation value of the new delivery plan is superior; and

(7) means for outputting the selected delivery plan;

wherein a total operating time of the plurality of delivery vehicles is one of the factors of the evaluation value of each delivery plan and the logic for calculating the evaluation value includes

logic for acquiring a first travel time from the distribution center to the first destination on a given route,

logic for modifying the first travel time by a first coefficient k₁,

logic for acquiring a second travel time from the last destination to the distribution center for the given route,

logic for modifying the second travel time by a second coefficient k₂, and

accumulator logic for calculating the total operating time of the route using the modified first and second travel times and the actual inter-destination delivery times for destinations on the route.

5. The computer system as defined in claim 4 further including logic for reiterating the calculation of delivery plans until the comparison logic indicates no further improvements in evaluation values are being obtained.

6. The computer system of claim 5 wherein the each of the coefficients k₁ and k₂ has a value between 0 and 1 and the modifying logic includes logic for multiplying the acquired first and second travel times by the associated coefficient.

7. A computer program for creating a delivery plan that includes a plurality of delivery routes, each route starting at a distribution center, including one or more destinations and ending with a return to the distribution center, the computer program causing a computer system to execute the steps of:

(1) generating a tentative delivery plan using data of delivery instances stored in the memory;

(2) calculating an evaluation value for the tentative delivery plan;

(3) executing an operation that alters the topology of the tentative delivery plan to generate a new delivery plan;

(4) calculating an evaluation value for the new delivery plan;

(5) comparing the evaluation value of the tentative delivery plan to the evaluation value of the new delivery plan;

(6) where the evaluation value of the new delivery plan is superior, substituting the new delivery plan for the tentative delivery plan; and

(7) causing the processor to output the selected delivery plan,

wherein the evaluation value for a delivery plan is based on the accumulated delivery times for the delivery routes included in the plan, and

each of the steps (2) and (4) of calculating the evaluation values further including the steps of, for each route in the delivery plan,

establishing a first travel time from the distribution center to the first destination on the route,

modifying the established travel time by a coefficient k₁ to calculate a first value,

establishing a second travel time from the last destination to the distribution center for,

modifying a second travel time by a coefficient k₂ to calculate a second value, and

using the modified travel times and the actual inter-destination delivery times in calculating the evaluation value for each route in the delivery

8. A computer program as defined in claim 7 wherein the computer program further causes the computer to perform the steps of reiterating steps (1) through (6) until it is determined that no further improvements in evaluation values are obtained.

9. A computer program as defined in claim 8 wherein the each of the coefficients k₁ and k₂ has a value between 0 and 1 and the computer program causes each of the first and second travel times to be modified by multiplication with the coefficient associated with the travel time.