Keywords

1 Introduction

In its recent study for traffic linkages in Germany the Federal Ministry for Transport, Building and Urban Development (BMVBS) forecasts a substantial growth of the traffic volume in road haulage up to the year 2025 [1]. Especially the long-haul road transportation contributes to this trend. A growth of transport volume of about 55 % and an increase in traffic of about 84 % is expected. From the ecological and the economic point of view, these trends should not only be faced with an adjustment of the road network, but also with a more efficient use of the existing infrastructure [2]. In Germany, every fifth truck in commercial freight traffic is already driving without any load at all [3].

The Project “CloudLogistic” – funded by the state North Rhine-Westphalia of the Federal Republic of Germany and by means of the European Regional Development Fund (ERDF) – addresses these challenges. “CloudLogistic” focuses its research on a more innovative logistics concept for freight cooperation to strengthen the market position of Small and Medium-sized Enterprises (SME). In this concept the strengths of already existing general cargo and Full Truck Load (FTL) networks are transferred to the area of Less than Truck Load (LTL) transports.

Usually it is not possible for a Small and Medium-sized Logistic Service Provider (LSP), to transport several LTL shipments together in one truck because there are not enough shipments within similar source and target areas. Hence, for a single LSP, several trucks are required for the transport of several LTL shipments. The basic idea of “CloudLogistic” is to bundle LTL shipments of several cooperating LSP’s, via a cooperation network, by combining corresponding LTL shipments to generate synergetic effects. Therefore, the “CloudLogistic” concept relies on a line-based logistics model.

The addressed problem deals with the assignment of a set of shipments to a set of freight routes in order to minimize unused cargo volume of the vehicles. The assignment of each shipment is restricted to a subset of freight routes. Furthermore, the shipment has to be delivered in a specific time window. Thus, it is necessary to determine an order of shipments for each freight route that guarantees the observance of all time windows.

2 Related Work

The described problem of shipment assignment corresponds with the problem [4] that is worked out as a mathematical model in the form of an Integer Linear Program (ILP). Analogues to the literature taxonomy this problem was classified as “Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Assignment Restrictions” (m-VRPTWAR). Paper [5] has established a heuristic for the implied evaluation of the feasibility of the m-VRPTWAR based on [4].

Since [6] first addressed the issue of vehicle routing problems, the subject has become an area of intensive research in logistics. In [7] a multilevel solution method has been shown for the “Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows”. First the algorithm determines reasonable clusters of nodes with the help of a heuristic approach. Afterwards, it distributes these nodes over the trucks in a valid order by solving a Mixed Integer Linear Program (MILP). The same problem class was covered by [8]. This work didn’t focus on the development of a solution method, but the development of an efficient mathematical formulation of the problem model. Considering the more general problem class of the “Vehicle Routing Problem with Time Windows”, the papers of [9–11] may be referred to.

3 The Cloudlogistic-Concept

Similar to the IT term “Cloud Computing”, the “CloudLogistic” concept describes the ability and opportunity of the LSP’s to share unused resources by participating in a freight cooperation network. This is done by using its infrastructure, its resources and scaling them locally while even sharing their own infrastructure and resources with the network. The basic principle is visualized in Fig. 1. Several shipments of different network-partners will initially be bundled and assigned to previously established freight routes (A). Each route is operated by a partner of the cooperation. For a combined disposition of LTL shipments, freight routes are established, i. e. the relation between a source and a target area that is operated regularly by several trucks via point-to-point transportation (B). The trucks are provided by the cooperating partners. Shipments will be collected in the source area of the route and then carried without any turnover directly to the corresponding target area, where they are locally distributed (C).

Fig. 1
figure 1

Visualization of the “CloudLogistic-Concept”

Full size image

The basic aim of the “CloudLogistic” concept is to determine an assignment of shipments to a certain set of freight routes while decreasing the number of needed trucks, respectively the needed FTL capacity. Other goals like the minimization of the distance in the target area, the minimization of the total cost or a multi-criterian goal could also be implemented. The CloudLogistic-approach initially assumes – based on the investigations of [3] – that the ecological and the economic benefits of the overall optimization potential is maximized if the minimization of the needed FTL capacity is chosen as the main optimization goal. The assignment of shipments to a set of certain freight routes is classified as a NP-hard optimization problem [4]. The problem is illustrated in Fig. 2.

Fig. 2
figure 2

Visualization of the assignment problem

Full size image

First, shipment A is pushed into the system – which can only be assigned to freight route 2. In contrast, both routes are feasible for the transportation of shipment B. If shipment B is assigned to freight route 1 and freight route 2 does not have sufficient unused capacity, shipment C may not be delivered because C can only be assigned to freight route 2. The number of such collisions increases, if the source and target areas of multiple freight routes overlap and additionally a large number of corresponding shipments have to be distributed.

4 Requirements for the Shipment Processing

The “CloudLogistic” concept represents a novel freight cooperation model. To realize this concept the creation of software-based centralized solutions which fulfil the requirements of the inducted business processes is needed. One of the main processes, which have yet to be investigated, is the processing step for new shipments pushed into such a kind of system. In this section the main requirements for shipment processing are discussed.

As explained above, the formation of freight cooperation is intended – in contrast to common freight exchanges. Therefore, the shipment processing has to ensure that all accepted shipments can and will be delivered and consequently, can be allocated to a certain freight route. Otherwise, the shipment will be rejected. This essential requirement has far-reaching consequences for the design of the architecture, the construction of the needed software-based platform and used optimization techniques. If there is not enough capacity to deliver all shipments or the assignment always fails because there occur other conflicts like violation of the defined time windows, no assignment can be found. The existence of such a situation has to be prevented. Therefore, the existence of a fitting assignment has to be ensured to make sure that all shipments can and will be delivered.

For this purpose the shipment processing has to be split into two components, as shown in Fig. 3. The first component represents the evaluation of the feasibility that incrementally checks if a new shipment can additionally be assigned to a certain freight route. It has to be ensured that an allocation that fits all restrictions for each shipment and freight route always exists. If no assignment can be determined, then the shipment may not be accepted by the freight cooperation. On the other hand a component is needed, which represents the final optimization step. This step has to calculate the optimal allocation of shipments to corresponding freight routes under the defined restrictions.

In the following part some basic requirements for both introduced components are described. Firstly the requirements for the final optimization techniques are addressed. Then they will be supplemented by additional requirements for the pre-processing phase and the evaluation of the feasibility. These requirements have to be taken in to account for developing the platform. The requirements are summarized in Table 1. In addition to the requirement analysis the use of realistic test data is essential to evaluate different implementations of the whole shipment processing step. In the following a method for the generation of realistic test data will be introduced.

Fig. 3
figure 3

Overview of the fundamental IT-based shipment processing steps

Full size image
Table 1 Requirements for the multilevel shipment processing
Full size table

4.1 Capacity-Based Constraints

In addition to the formulated optimization target, there are several restrictions which have to be considered by the optimization. One of these restrictions is given by the total capacity of the freight routes. The capacity of a truck is defined by the maximum load weight and the corresponding number of loading meters. The considerations of driving and rest times of the truck drivers, as well as the observance of pick-up time windows, do not matter for the main optimization problem at this time.

4.2 Time Window-Based Constraints

In contrast, it has to be ensured that the delivery time window is accurate. Therefore the optimization step has to calculate a possible delivery sequence for each freight route in which the shipments are deliverable. The delivery sequence has to consider unexpected delays, like traffic jams or delays while unloading in terms of appropriate temporal buffers.

4.3 Routing-Based Constraints

A further requirement addresses a special property of the introduced logistic model which is denoted in the following as an assignment restriction (according to [12]). For each shipment a set of freight routes which is able to handle the assigned shipments is defined. Therefore a shipment cannot be assigned to all available freight routes. An obvious allocation constraint is created by the source and target areas of the freight route. A shipment can only be assigned to routes, where source and target areas cover the pickup coordinates and the destination of the shipment.

4.4 Additional Assignment Constraints

Restrictions concerning certain shipment types respectively some categories of goods (i.e. dangerous goods) also need to be taken into consideration. Additionally, different optimization goals lead to a combined multicriterian definition. Especially the use of a fairness model, which prefers or punishes certain LSP’s, the goals of the national economy, the goals of the LSP’s and the goals of the freight cooperation as an independent company are competing against each other. The possibility of an expansion and adaption of the optimization process considering such constraints has to be taken into account.

4.5 Optimization Step Time Constraint

There are some given performance requirements for the optimization process. The calculation of an optimal allocation of shipments to freight routes has to be completed within a period of 1.5 h on a defined test system. A longer time for the processing step is not acceptable to ensure a frictionless integration into the running business processes of the LSP’s.

4.6 Feasibility Check Time Constraint

The requirements presented up to this point, except the non-functional requirement R5, are also requirements for the processing step of the feasibility evaluation. For this step, more restrictive performance requirements have to be met. The feasibility check has to be able to handle shipments requests as quickly as possible, so that waiting periods for the LSP’s not arise. The notice for acceptance or rejection of a shipment has to occur within seconds. Since there is no reliable history data about the frequency of receiving shipments of LTL cooperation networks, the order of an existing general cargo network of an average business day shall be used as an indicator (Fig. 4). Accordingly, the feasibility check has to process 50 shipments per minute at maximum.

4.7 Pre-Processing Time Constraint

The pre-processing step shown in Fig. 3 is needed to determine the geographical coordinates of the shipments origin and its destination. Additionally, it has to be determined which freight routes are suitable to deliver the shipment under consideration of all known restrictions. In this case, a lot of temporal distances have to be determined using a software-based routing planner. Naive approaches would produce thousands of unnecessary distance requests. This would hurt temporal constraints given here. A time line of a few seconds must be observed, for example, by using appropriate index structures to significantly reduce the number of distance requests.

In addition to the requirement analysis the use of realistic test data is essential to evaluate different implementations of the whole shipment processing step. In the following a method for the generation of realistic test scenarios will be introduced.

Fig. 4
figure 4

Orders of a general cargo freight cooperation

Full size image

5 Test-Data Generation

In context to the introduced “CloudLogistic” concept and to the evaluation of solutions for its implied optimization and feasibility problems, the use of realistic test data is essential. So, a set of test data shall illustrate a nearly realistic compilation of freight routes and shipments. Besides the generation of realistic test data, it is also conceivable using different (and sometimes unrealistic) worst-case-scenarios for the tests to evaluate a solution method even in such extreme cases. To give an example, the allocation limit for all shipments could be eliminated. This would dramatically increase the possible combinations of shipment and freight routes and it would be difficult to evaluate the applicability of the solution method for treating this problem. Instead, the applicability of an algorithm for solving a general optimization problem of the class m-VRPTWAR would be evaluated. The following assumptions are the results of requirement workshops with experts in logistics and different experts of local LSP’s.

It is reasonable to choose the distribution of companies across Germany as an indicator for the distribution of realistic source and target areas. It also is reasonable to generate shipments corresponding to these areas. For the freight routes themselves a realistic extension of the area is assumed. For simplification source and target areas are defined as Euclidean circles. For the generation of test data the Euclidean model holds and is easily changeable to other approaches. Here a source area with an extension of 5– km and for the target area an extension of 10–50 km is considered to be realistic. For a single shipment all other parameter besides the source and target location are needed. Those are the number of needed loading metres, the weight and the time period for unloading. In our definition a LTL shipment usually consist of 7–27 pallets. For each pallet 0.4 loading meters as well as a random weight of 100–800 km is valid. For unloading a time period of 1–2 min for each pallet is considered. The time window for the delivery is chosen randomly between 8:00 a.m. and 6:00 p.m.

For the generation of test scenarios a tool has been developed. It realizes a projection of the distribution of German companies (Fig. 5) to a probability distribution. For densely populated regions (in the map shown as dark regions) a higher probability is assumed. For sparsely populated regions (in the map shown as bright regions) a lower probability is chosen. Using the presented tool (based on the shown probability distribution) randomized coordinates will be chosen and used as center of the source and target areas. Figure 5 shows a screenshot of the developed tool and an example of generated source and target areas as certain freight routes as well as the source and target locations of several shipments.

Fig. 5
figure 5

Screenshot of the developed tool for test data generation

Full size image

In order to evaluate the goodness of the feasibility check the number of shipments which are rejected incorrectly has to be identified. If a shipment is generated as described previously and if this shipment is refused by the feasibility check, we don’t know whether it was rejected because it could not be scheduled or whether the feasibility check didn’t found the matching assignment. Therefore it has to be ensured that all shipments of a test case can be scheduled. Then a useful evaluation of the feasibility check is possible. In addition the behaviour of a solution method shall be investigated, in case the available trucks are already reaching their capacity limits.

So, to evaluate a solution which represents the feasibility check the generation of shipments has to be changed slightly. First a number of freight routes are generated according to the assumptions above. In a second step shipments are created by dividing the available capacity of the freight routes in certain pieces according to the restrictions and assumptions we made for the shipment properties. Then for each piece a source and a target location within the source area respectively the target area of the freight route is randomly selected. For the generation of realistic and practicable delivery time windows the time span of 8 a.m. to 6 p.m. will be divided into intervals of equal size according to the partition of the freight capacity. The delivery time windows for each shipment now are generated by a randomized deviation around the intervals central point. This approach ensures that all shipments can be scheduled within its spatial and temporal requirements and there are enough shipments for reaching the capacity limit of all freight routes. Moreover, such kind of scenario can be assumed as realistic.

6 Evaluation of the Feasibility-Check

In addition to the in [5] presented Repacking First Fit algorithm (called RFF) as a first implementation of a feasibility check, based on the here introduced generation of test data a scenario with 3500 freight routes and 14495 shipments was used to additionally evaluate different repacking depths. The RFF algorithm first tries to find a freight route to which the shipment can be assigned, using a first fit approach. If no such freight route exists, the repacking-phase is initiated. Thereby it is tried to take back an already assigned shipment in such a way, that the freight route is preferably filled completely, after assigning the new shipment to it. On the one hand this approach is supposed to make room for the new shipment; on the other hand it ensures that as the cargo volume of the freight routes is utilized as much as possible.

Fig. 6
figure 6

Rejection rate of the RFF algorithms for using different repacking depths

Full size image

A more detailed description of the algorithms is presented in [5]. Figures 6 and 7 show the results of the evaluation of the RFF algorithm for eight different repacking depths and for a scenario without any repacking step.

As presented in Fig. 6 the use of a repacking approach significantly reduce the ratio of rejected shipments. By scaling up the repacking depth the ratio of rejected shipment decreases logarithmical. Corresponding to the rejection rate in Fig. 7 the required execution time is shown in order to check all shipments in terms of ability to deliver. Here by scaling up the repacking depth the derivation of each function increases exponentially resulting in increasing execution time for a single shipment. Considering Fig. 7 with a repacking depth of 6 the execution time raises up to 37.9 ms. So a violation of the introduced feasibility check time constraint – “At least 50 shipments per minute have to be tested” – is not given. In this case the rejection rate in the given scenario decreases down to 7.77 %. The choice of a higher repacking depth leads to a marginal decrease of this ratio. For reaching an optimal result the repacking depth can be chosen dynamically with respect to the current number of requests.

The measurements were carried out on an Intel Core 2 Quad Q9650 CPU with 4 Cores (3.0 GHz each) and 8 GB RAM. Windows 7 Professional 64-bit has been used as operating system. Furthermore the Java Virtual Machine (JVM) of SUN Java Development Kit (JDK) 1.6.0-20 has been employed, since the reference implementation of the heuristic method has been programmed in Java.

Fig. 7
figure 7

Execution time of the RFF algorithms using different repacking depths

Full size image

7 Conclusion and Outlook

In this paper, the problem class m-VRPTWAR developed in [4] and [5] was transferred to the application domain of the “CloudLogistic” concept. For this purpose, the concept was presented in its fundamentals. Based on this description, the basic requirements for the shipment processing within an implied cooperation platform have been developed. By doing this, the shipment processing has been divided into two separate phases. We developed a set of basic requirements for the feasibility check, as well for the final optimization and as well for the pre-processing of the shipment data and their preparation. Based on these requirements, the generation of test data was introduced. In the development of the test data generator, in particular the unique requirements of the multi-staged shipment processing were considered.

By using the described generator tool different realistic test scenarios are generated automatically. These scenarios were used for the evaluation of the feasibility check and the final optimization process.

An extension of the in [5] introduced evaluation of the RFF algorithm was used as an example for using the generated test data to reflect the investigated requirements. In further research it should be deferred to the extension of the first as circular assumed area schema to an elliptical model. Here the used Euclidean approach is converted into a time-based model with isochrones. Also the construction of an index structure for decreasing the number of distance queries and speeding up the whole pre-processing is a focus of future research.