JP2001034881A - Delivery planning support device - Google Patents

Abstract

(57) [Summary] [Problem] To make a vehicle allocation plan for each of a plurality of delivery areas by a saving method, reduce the number of trucks with less than the total of all areas, and improve the efficiency of truck delivery as a whole. Provide a delivery plan support device that can Here, the less-than truck means a truck having a vacant state where a predetermined transport function is not satisfied. As a first step, a normal saving method is executed for each of the delivery areas 1 to 7, and a track with a smaller amount generated therein is determined. By temporarily collecting, setting the temporary area 9 and executing the saving method again in it,
Minimizing the generation of the low-volume trucks by sharing the low-volume trucks generated as a result of planning the vehicle allocation by the saving method in a plurality of areas is minimized.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of determining a vehicle allocation in a plurality of areas by a saving method, determining a smaller quantity of trucks in each area, automatically collecting them, and reallocating the trucks. The present invention relates to a delivery plan support device that enables the user to perform the delivery plan. Note that a less-than truck means a truck having a vacant state where a predetermined transport function is not satisfied. For example, the loading capacity, the number of delivery destinations, and the operation time are smaller than a maximum value (full capacity) by a predetermined amount. This corresponds to a small amount (for example, 60% or less of the full amount).

[0002]

2. Description of the Related Art An algorithm called a simulated annealing method, a genetic algorithm, or a saving method is used in a delivery plan support apparatus. Above all, the saving method is generally used because an accurate solution can be obtained relatively easily. However, since the saving method is a solution in a case where there is an unlimited number of trucks required for vehicle allocation, if the necessary number of trucks are prepared at the time of executing the saving method, a smaller amount of trucks may be generated. For example, with regard to the loading capacity, if the maximum loading capacity of each truck is 2.0 tons and the total transported quantity of that day is 8.1 tons, four full loaded trucks and one 0.1 ton are transported. There is a case where a track is generated. A track having an empty state like this track is referred to as a less-than-quantity track. In addition, the number of delivery destinations (for example, up to 20 locations) and the operation time (for example, up to 10 hours) may be similarly reduced. Usually, a delivery plan does not collectively carry out hundreds of delivery destinations (nodes), but divides them into predetermined delivery areas set in advance (for example, each ward in Tokyo or an area near a delivery route). Since the saving method is applied to each delivery area, there is a possibility that a smaller amount of trucks is generated for each area, and a maximum of less quantity trucks equal to the number of delivery areas is generated. This may result in an inefficient vehicle allocation plan as a whole.

[0003]

As described above, in the method using the conventional saving method, there is a problem that a less-than-light truck is generated for each delivery area, resulting in an inefficient dispatching plan as a whole. was there.

SUMMARY OF THE INVENTION The present invention has been made to solve the problems of the prior art as described above. When a vehicle allocation plan is made for each of a plurality of delivery areas by the saving method, the total amount of all the areas is reduced. It is an object of the present invention to provide a delivery plan support device capable of reducing the number of trucks and improving truck delivery efficiency as a whole.

[0005]

Means for Solving the Problems In order to achieve the above object, the present invention is configured as described in the claims. That is, in the present invention, first,
As a first step, a normal saving method is executed for each delivery area, and the smaller amount of trucks generated therein are determined. As a second step, the smaller amount of trucks generated there are automatically collected and temporarily stored. By setting a delivery area and executing the saving method again in it, the less-than truck generated as a result of making a vehicle allocation plan by the saving method can be shared by multiple areas to reduce the less-than truck. To minimize it. With such a configuration, when a person dispatches a vehicle, the delivery destination that has been left little by little in a plurality of areas is delivered by one truck across the areas, and an optimal result close to the result of reducing the number of trucks as a whole is obtained. The result can be obtained.

[0006]

According to the present invention, the processing is complicated and the implementation and understanding are complicated by sharing the smaller-volume trucks generated as a result of planning the distribution by the saving method for each delivery area in a plurality of areas. Without using a simulated annealing method or genetic algorithm that is difficult to implement, the algorithm is simple and the saving method that is easy to implement and understand is used to reduce the number of trucks less than the total of all areas and deliver trucks as a whole The effect is that the efficiency of the method can be improved.

[0007]

FIG. 1 is a conceptual diagram showing the relationship between a delivery area and a delivery center (departure place, return place) in the present invention. In FIG. 1, the entire area is divided into seven delivery areas 1 to 7. A circle indicates a delivery destination (node: customer) 8. Departure from delivery center 10 and delivery destination 8
And the black line returning to the distribution center 10 indicates a route for delivery by one truck. Although the delivery destination 8 is shown only in the delivery area 6 in FIG. 1, the delivery destination 8 actually exists in other delivery areas. Further, a delivery plan support device 11 is provided in the delivery center 10, and drafts a delivery plan. The delivery center 10
May be provided for each delivery area or may be provided in common for a plurality of delivery areas, but the overall delivery plan is made by one delivery center.

FIG. 2 is a block diagram showing an example of the configuration of the delivery plan support device 11. In FIG. 2, the input device 21
Is a keyboard, for example, and inputs various operation signals, customer data, track data, and the like. Output device 22
Is a display device such as a liquid crystal display device or a CRT display device, or a hard copy device such as a printer, and outputs a delivery plan of a calculation result. The input / output interface 23 performs signal conversion and matching between the input device 21 or the output device 22 and the arithmetic device 24. The arithmetic unit 24 is, for example, a CP
U, which calculates the delivery plan according to the signal input via the bus 26 and outputs the result. The memory 25 is a disk memory, a RAM, a ROM, or the like, and stores customer data and track data, and data during various calculations.

FIGS. 3 and 4 are flowcharts showing an embodiment of the calculation method. 3 and FIG.
,, Are connected to each other. First, in FIG. 3, data is input in step S501, and in step S502, a customer database and a track database are created and stored in the memory. The customer database is the customer information of the delivery destination, and the location of the delivery destination (town name, location,
Address, latitude, longitude, etc.), time constraints (delivery time, etc.), amount of cargo, and the like. In addition, the truck database includes information such as the maximum loading capacity, departure and return positions, operation time, and departure time for each truck. The customer database and the truck database are stored for each delivery area.

Next, in step S503, a travel cost is calculated based on the customer database, and the calculated travel cost is stored as a distance database. To be precise, the distance database contains the travel distance between customers, travel time, fuel cost,
Although it is a moving cost including a personnel cost and the like, in the case of simplification, it can be represented only by a moving distance between customers, for example.

Next, in step S506, a saving value is calculated for each track based on the distance database and the track database, and a saving matrix is created. Hereinafter, the calculation of the saving value will be described. The calculations in steps S506 to S518 are performed for each delivery area.

FIGS. 5A and 5B are diagrams for explaining a method of calculating a saving value according to the ordinary saving method. FIG. 5A shows a case where the departure place and the return place are the same place, and FIG. Are different. First, as shown in FIG. 5A, when the departure place and the return place are the same, the departure place node0
From (node 0), the delivery destinations nodei (node i) and n
Consider a case where delivery is made to an odej (node j). Assuming that distances between the nodes are d0i, d0j, and dj, node0 → nodei can be used for piston transportation (simply go from the departure point to each destination and return).
→ The saving distance in the case of traveling to nodej is expressed by the following (Equation 1). Sij = (d0i + d0j) × 2− (d0i + d0j + dj) = d0i + d0j−dj (Equation 1) The value of (Equation 1) is called a saving value.

When a saving matrix in which saving values are calculated for all combinations of nodei and nodej is created, and the nodes are merged in order of increasing saving value, a vehicle that is nearly optimal can be allocated. For example, when Max (S) = Sij, nodei, n
odej will be merged into a route that can be carried on one truck. At this time, if the conditions of the truck (maximum loading capacity, etc.) cannot be observed due to the merger, the merger will not be performed.
As a merger candidate.

Further, as shown in FIG. 5B, the saving value when the departure point and the return point are different can be extended as shown in the following equation (2). In FIG. 5B, n
odem (node m) is a return point different from the departure point node0. s1 = d0i + dmi + d0j + dmj- (d0i + dij + dmj) = dmi + d0j-dj s2 = d0i + dmi + d0j + dmj- (d0j + dj + dmi) = dmj + d0j-dj-dj-dj-djm It is a saving matrix when the land and the destination are different.

Next, returning to FIG. 3 again, step S507
Then, a combination of delivery destinations giving the maximum saving value in the saving matrix is searched. For example, when Smn is the maximum as the saving value in the saving matrix, the delivery destination node m and the node n are merging candidates.

Next, in step S511 (step S509 will be described later), it is determined whether or not the respective constraint conditions are satisfied when the merging candidate node mn is merged with the track t. For example, it is checked whether the maximum load, the maximum number of delivery destinations, and the maximum operation time of the truck t are exceeded due to the merger. If the constraints are satisfied, merging is actually performed in step S513. Otherwise, do not merge. Regardless of whether or not the merging is performed, all the saving values of the merging candidates are reset to 0 in step S512, so that the merging candidates will not be merged in the next and subsequent times. Then, the process returns to step S507, and the processing after the maximum saving value search is repeated.

In step S509, it is determined whether Smn = 0. That is, all the merging candidates are inspected, and if all the saving values become 0, step S518
Go to

In step S518, it is determined whether or not the delivery truck of each route is a small quantity truck. The criterion of the under-volume truck is, for example, that the loading capacity is less than 60% of the maximum loading capacity and the number of delivery destinations is the maximum number of delivery destinations (for example, 20
If any one of the following is less than 60% of the maximum operating time (for example, 10 hours) and the operating time is less than 60%, it is determined that the truck of the route is in the less amount and the marking is made. . In addition, any one or two of the above-mentioned loading amount, the number of delivery destinations, and the operation time may be used as the criterion of the under-volume truck. In addition, the above-mentioned less than 60% is an example, and may be appropriately set according to the actual situation.

Steps S518 in FIG. 3 to steps S521 and S520 in FIG. 4 and step S520 in FIG.
By returning to step S506 via 519,
The above matrix creation, search, merger, and determination processes are performed for all delivery areas.

If it is determined in step S520 in FIG. 4 that all the areas have been completed, in step S514, the delivery destination belonging to the route assigned to the truck marked as the less-volume truck in the entire delivery area is provisionally determined. Create a temporary customer database as a customer. Step S
At 515, a track database for the above-mentioned less-than-quantity track is created.

Next, returning from step S515 in FIG. 4 to step S503 in FIG. 3, the temporary customer database is set as one temporary delivery area, and the temporary customer area is used in step S5 by using the track database for the less-than-light truck.
From 03 to step S518
Perform search, merge, and judge processing. That is, a distance database is calculated using the temporary customer database, and a saving value is calculated using the track database and the temporary database to create a saving matrix, and the temporary customer database is used as one temporary area to perform search / merge by the saving method.

In step S521 of FIG. 4, it is determined whether or not the temporary area is to be processed. If the temporary area is a temporary area, it is determined that all processing has been completed, and the result of the calculation is determined in step S508. Output. The calculation results to be output include a delivery route of a truck (a delivery destination to be delivered and its route) for each delivery area and a delivery route (a delivery destination to be delivered and its delivery route) when a less-than truck is shared for a temporary area. Route). FIG. 6 is a conceptual diagram showing the temporary area. In FIG. 6, the area surrounded by the curve is the temporary area 9, and the saving method is applied within this area.

As described above, in the present invention, in the first stage, a normal saving method is executed for each delivery area,
In the second stage, the less trucks generated there are automatically collected, a temporary delivery area is set, and the saving method is executed again in that area. By sharing the generated small quantity track in a plurality of areas, the occurrence of the small quantity track can be minimized. This means that when a person dispatches a vehicle, an optimal result close to the result of reducing the number of trucks as a whole by distributing the remaining destinations little by little in a plurality of areas by one truck across the areas is obtained. be able to.

[Brief description of the drawings]

FIG. 1 is a conceptual diagram showing a relationship between a delivery area and a delivery center in the present invention.

FIG. 2 is a block diagram showing an example of the configuration of a delivery plan support device 11.

FIG. 3 is a part of a flowchart illustrating an embodiment of a calculation method.

FIG. 4 is another part of a flowchart showing an embodiment of a calculation method.

5A and 5B are diagrams for explaining a method of calculating a saving value by a saving method, wherein FIG. 5A shows a case where a departure place and a return place are the same place, and FIG. 5B shows a case where a departure place and a return place are different. FIG.

FIG. 6 is a conceptual diagram showing a temporary area.

[Explanation of symbols]

 1 to 7: Delivery area 8: Delivery destination (node) 9: Temporary area 10: Delivery center 11: Delivery plan support device

Claims (2)

[Claims] 1. A system for drafting a delivery plan for delivering a delivery destination belonging to each delivery area by a plurality of trucks to a plurality of delivery areas, comprising: a delivery destination data for each delivery area; A track database storing an attribute of each truck used for delivery; a distance database calculating means for calculating a distance database corresponding to a moving cost between customers based on the customer database; Saving matrix calculating means for calculating a matrix of saving values between delivery destinations based on the distance database; searching means for searching a combination of delivery destinations having the largest saving value from the saving matrix; and the searched delivery destination Restrictions when merging routes to which Is determined, and when it is determined that merging is possible, the routes to which the respective destinations belong are merged, and the element of the saving matrix corresponding to the searched combination of the destinations is set to 0. Merger determination means, and when a truck having a vacant state where the predetermined transport function is not satisfied is designated as a less-than truck, a less-than truck determination means for determining a less-than truck existing in the route, A temporary customer database is created with the delivery destination belonging to the route assigned to the truck determined to be a small-volume truck in all the delivery areas as a tentative customer. Using a database, calculating the distance database for the temporary area, saving matrix And a means for sharing a smaller quantity truck across the respective delivery areas by performing processing of creation, search, and merger. 2. The criterion for determining a lower-volume truck in the lower-volume truck determining means is that the loading capacity of the truck is less than a predetermined ratio of the maximum loading capacity, the number of delivery destinations is less than a predetermined ratio of the maximum delivery destination, and the operation time is shorter. If at least one of the three conditions less than the predetermined ratio of the maximum operation time is satisfied, the track is determined to be a track with a small quantity, or any one of the three conditions
2. The delivery plan support device according to claim 1, wherein the determination is made on one or two, and when at least one of them is satisfied, the truck is determined to be a less-than-light truck. 3.