US 2003/0078802 A1Published application

Method, system and program for creating a delivery plan

AssigneeInternational Business Machines Corporation

InventorTakashi Yonezawa

Life of this patent

Estimating the term…

Loading patent…

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.

Claims9

Dependent claims

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 k1 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 k2 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.

12 more elements

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 k1,
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 k2, 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.

11 more elements

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 k1 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 k2 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

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/265,754Filed 7 Oct 2002
Priority: JP 2001-32354922 Oct 2001
Published: 24 Apr 2003
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06Q 10/08
Administration; Management: logistics, e.g. warehousing, loading or distribution; Inventory or stock management
G06Q 10/047
Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem":…
G06Q 10/06375
Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of…:…
G06Q 10/08355
Shipping: routing methods