Keywords

1 Introduction

Transportation logistics is a major area of activity in the logistics field. Efficient transportation requires both efficient flow of material and people, as well as careful coordination of the entities performing the transportation. It is the issue of coordination that has especially been addressed by the academic logistic problem, the vehicle routing problem [1], in which the task is to simultaneously divide transportation activities to transporting entities and design optimal transportation routes for these entities. The goal is typically to minimize the number of entities (for example vehicles) and the total distance they travel.

Vehicle routing problem has several variants, each of which address a different set of properties encountered in real-life transportation planning. The most common variants include vehicle routing problem with time windows, pickup and delivery problem, multi-depot vehicle routing problem, and vehicle routing problem with backhauls. One of the main challenges in deploying optimization methodology to the VRP is this heterogeneity of these details. Operators have differing requirements [2], and different models typically require different solution methods to be solved efficiently and effectively [3].

Vehicle routing problems have been solved with a large array of optimization methods, ranging from exact methods [1] to metaheuristics [4] and hyperheuristic [5] methods. The most successful approaches to date have combined several metaheuristic components with a set of strong local search operators [6]. The downside of this diversity is the complexity of choosing efficient methods for the problem at hand [3].

A third challenge for a widespread utilization of optimization methodology is the fact that many logistic operators are relatively small. This results, due to the complexities mentioned, in an inability to acquire the necessary expertise to select, configure and deploy vehicle routing systems in general. In this paper, we attempt to provide a lightweight process for easier deployment of these methods, and discuss the implications of the process to the future of the optimization solution methodology.

The paper is structured as follows. In Sect. 31.2, we provide a context for the study, in Sect. 31.3, we describe briefly the research approach used, in Sect. 31.4 we propose a framework for examining the adoption of routing systems, and in Sect. 31.5 describe the key findings so far in the context of the proposed framework. Finally in Sect. 31.6, we conclude and suggest areas for further study.

2 Background and Contribution

The presented study is conducted as a part of a larger research project which aims to significantly lower the costs of deploying optimization in small and medium enterprises and public sector. There are two main hypotheses that form the basis of the project. Firstly, the utilization of optimization would provide value to SMEs and public sector institutions, and secondly, the observed lack of utilization is due to problems in deployment, and not in the optimization models and methods themselves.

The reasons for the above mentioned hypotheses are twofold: first, we have noted the success stories of the large-scale entities in deployment of optimization, indicating that the state of the art has advanced sufficiently for practical use, and second, the problems found in SMEs and public sector institutions exceed the efficient planning capabilities of the human dispatchers, i.e., they are non-trivial in most cases. In addition, our preliminary results indicate that there is a widespread demand for optimization solutions within SMEs, due to, for example, cost and environmental pressures.

It is still not clear which are the main reasons for the difficulty of the deployment in a scalable manner, and this paper presents the preliminary findings of our study. We have applied the process described in this paper in several cases, in organizations of different sizes and types. More specifically, we attempt to answer the following questions: why has commercial vehicle routing problem not been widely adopted, what are the barriers for the technology adoption, and especially, how do the findings affect the requirements for new vehicle routing problem models and solution methods. We propose a novel perspective to vehicle routing, and complement the already identified real-life aspects of commercial routing [7]. Our objective is to provide the SMEs with efficient tools for transportation planning in a scalable manner.

By efficient we mean accounting for the individual characteristics of the different cases well—unlike many of the current off-the-shelf routing systems which assume that one rich enough model and versatile enough algorithm set suffices. This has led to situation where systems either handle the simple cases (but as such do not provide enough value over the manual planning), or result in too complicated deployment and use in the complex cases. This has, effectively, lead to inefficient use of routing systems where most users do not benefit from the recent advances in the vehicle routing research. Thus to provide the efficiency needed by the heterogeneity of the SMEs, we derive additional requirements for the optimization methodology in this context.

To understand the scalability of the deployment, we identify several adoption barriers from the studied cases, and utilize a distinction frequently identified in EA frameworks: the domains—or layers—of business, data, and applications [8].Footnote 1 We build our deployment framework according to these three layers, categorize the barriers according to thess proposed framework, and suggest strategies for lowering them.

Previous studies has identified the need to consider commercial setting in general, and many of the publications on rich VRP variants have addressed the issue of modeling the aspects commonly found in real-life routing cases [7], as well as constructing systems capable of incorporating these aspects [9]. However to our knowledge, EA theory has not been applied to analyzing VRP solution methodology in this manner.

3 Research Method

The research is ongoing and is conducted as a prospective case study. More specifically, we offer optimization for deployment, pilot use, and operational use to several small and medium enterprises and public sector institutions and observe issues during the process.

In practice, we have studied the adoption (or the reason for not adopting in some cases) of routing systems in 12 distinct cases at this point of the study. We refer to these cases with letters from A to L. The characteristics of the cases are briefly described as follows:

  • A—A medium-sized enterprise operating nationally with more than hundred trucks for serving several distribution centers.

  • B—A newspaper with internal transportation activity of less than ten trucks for daily deliveries of the publication on a regional level.

  • C—A regional transportation company with less than 30 trucks for delivering goods and distributing free papers.

  • D—A public sector entity with mission critical transportation tasks with several dozens of vehicles at a time.

  • E—A public sector entity with 30 vehicles performing mission critical people transportation on a regional level.

  • F—A regional transportation company with less than 20 trucks for delivering goods and packages.

  • G—A food production establishment employing an internal fleet of less than 20 vehicles for transporting perishable goods with strict time limits.

  • H—A medium sized municipality for providing school transportation service.

  • I—A small municipality for providing school transportation service.

  • J—A medium sized municipality providing school transportation service within both urban and peripheral areas.

  • K—A medium sized nationally operating enterprise employing a fleet of 25 tanker trucks.

  • L—A single vehicle courier service providing internal post delivery service for a municipality.

The cases were studied by analyzing the requirements, performing the deployment and observing and interviewing the case stakeholders, both end users and the individuals responsible for the procurement of ICT systems. From the studied cases we formulated a framework for analyzing the barriers of adoption and describe the identified barriers along with suggestions for lowering them. These are described in the two subsequent sections, respectively.

4 Proposed Framework

Although the stage of the research does not allow for quantitative analysis of the issues, we present the preliminary findings of the study with respect to the emerging process. One interesting finding is that the connection to the enterprise architecture theory also affects the optimization methodology design in a subtle manner, which we explain in detail shortly.

The proposed framework is designed to answer the necessary hypotheses for vehicle routing system adoption in a given case. The first hypothesis is the hypothesis of value, which assumes that the vehicle routing system can provide added value to the operation of the enterprise. The second hypothesis is the hypothesis of data, which assumes that the data needed for the transportation optimization exists or can be generated in sufficient quality (EA data layer). The third hypothesis is the hypothesis of process, which assumes that the way of working does not change such that it undermines the other operations of the enterprise (EA business layer). The final hypothesis is the hypothesis of system, which assumes that the existing systems in the enterprise can be complemented by the new vehicle routing system (EA applications layer).

Fig. 31.1
figure 1

The deployment process framework and the related aspects of the enterprise architecture layers

Full size image

The deployment framework and process is outlined in Fig. 31.1. The process consists of the following steps. First a Concept Check is performed to ensure that the operator does actually require a VRP optimization solution (hypothesis of value). In Configuration Selection, the requirements of the operator are mapped with the aid of an optimization expert. Configuration is defined as the state of the variable settings of the system, including, most significantly, the optimization model and the optimization methods and their parameters. In Test Computation, the main aim is to ensure that the data required for the optimization process does exist and is valid (hypothesis of data). In addition, Evaluation is done for the selected configuration, based on the quality of the optimization results. After Pilot Use, the process of the operator has been adjusted to the use of automated transportation planning, and can be put into Operational Use (hypothesis of process). This finishes the deployment by integrating the other systems used by the operator with the optimization solution (hypothesis of system).

As we observe, there are three integration phases in the process: data, process, and system integration, which are also frequently identified in enterprise architecture theory.

Data required for optimization includes the necessary elements to construct the decision variables, constraints and objective of the optimization model. An important aspect is also the quality of data, more specifically, the data has to have a structure suitable for automated planning. One major issue has been data in free-form text where formal rules would be needed (e.g., incompatibility rules).

Process integration requires adjustments in the operational environment, some of which provide new opportunities for improvements. These include changes in planning frequencies, order processing capabilities, and the planning effort, all which, in many cases, affect the core of the operations of the logistic operator.

System integration consists of connecting the existing systems to the newly introduced planning tool. This includes introducing methods for data exchange and adjusting the necessary interfaces between the systems.

We have observed that the three phases of the process can be more easily managed during the deployment by keeping them separated. This also allows the operator to invest in the deployment gradually, as there is no need to start process integration if the data integration cannot be completed.

The successful deployment of the optimization system requires data, process, and system integration. However, all these phases require involvement of an optimization expert, which is prohibiting investment for SMEs. In order to make the deployment scalable, the process needs to be automated to be usable by a regular user. Note that this involves the change management during operations. In practice, changes in the requirements should be accommodated by the optimization model and methodology. This is a major requirement for the optimization methodology in the context of small and medium enterprises and public sector institutions.

5 Results

After formulating the deployment process framework, we attempted to identify the problems encountered in cases and pinpoint the exact phase of the encounter. This enables us to gather requirements and assumptions on not only the vehicle routing system itself, but also the optimization methods needed to solve the VRP instances in each case. We define barrier as a reason that prevents the user to start using a routing system unless changes to the system are made or other necessary manual activities are performed.We classified these reasons according to the phase of the deployment process it occurs.

5.1 Data Integration

We identified nine different data integration barriers for adopting the vehicle routing system. The most frequent problems concerned either the fact that some subset of the needed data was missing or there was not enough expertise to extract the data from existing systems. The following barriers were identified in the data integration phase:

  • D.1—Lack of data in digital form. The data needed for building the optimization model is available, but is not in a digital form.

  • D.2—Missing structure of data. The data needed for building the optimization model is available, but does not have a formal structure for automatic interpretation in the model building. Examples include descriptions of the compartment loading constraints in free-form text.

  • D.3—Missing task data elements. The data needed to describe the tasks of the route planning has missing elements, such as missing or partial schedule information, e.g., time windows.

  • D.4—Missing resource data elements. The data needed to describe the resources used on the routes, such as vehicles, has missing elements, such as speed profiles for different vehicle types.

  • D.5—Missing geographical information. The data needed to describe the geographic area where the transportation takes place is missing necessary data, such as digital map or some key characteristics of the road network.

  • D.6—Missing cost structure data. The data needed to formally evaluate the quality of the optimized plan is not available. Examples include hidden costs on loading and unloading vehicles and changes on the workflow on, e.g., warehouses due to changes in the routing procedures.

  • D.7—Inability to acquire data from existing system. The data needed for modeling and solving the VRP is available, but it cannot be transferred from the existing system for utilization of optimization.

  • D.8—Inability to combine data from several existing systems. The data needed for modeling and solving the VRP is available, but it is stored on several systems and not enough expertise is available to combine the data.

  • D.9—Low quality of existing data. The data needed for modeling and solving the VRP is available, but the quality of the data is not sufficient. Examples include error in addresses, order quantities or schedule constraints.

When data integration barriers have been cleared, we may proceed to the process integration phase.

5.2 Process Integration

We identified six process integration barriers for adopting vehicle routing systems. Many of the barriers resulted from the physical reality that cannot be captured by the vehicle routing models, including complex changes in costs, procurement procedures and perceived quality by both the users and their customers.

  • P.1—Inability to describe the required operating process characteristics to the system due to lack of expertise. The process of loading, packing, transporting and unloading involves operations whose cost, duration etc. depends on functions whose inclusion to the optimization model require more expertise than is available.

  • P.2—Prohibiting personnel role changes or other human resource issues. The employment of a vehicle routing system results in changes in the roles of the personnel, such that the enterprise is unable to adapt to the changes. Examples include the inability to train, e.g., order management personnel to the increasingly centralized transportation planning.

  • P.3—Customer satisfaction decrease due to change in processes. The employment of a vehicle routing system results in a perceived decrease in quality of service, such as differing driver visiting the customer in subsequent days.

  • P.4—Prohibiting changes in the physical operations. The employment of a vehicle routing system results in prohibiting changes in the physical operations, such as need to manually reorder deliveries in warehouses as an additional process step.

  • P.5—Lack of resulting plan quality. The plans produced by the vehicle routing system are not satisfying for the end user. Examples include underutilization of the fleet and obviously inefficient route sequences.

  • P.6—Opaqueness of the decision support leading distrust to plans. The plans produced by vehicle routing system indicate efficiency, but the user is unable to evaluate the feasibility of the plans in reality.

After the changes resulting from the routing system adoption have been incorporated to the existing processes, the vehicle routing system can be integrated to the rest of the systems of the enterprise.

5.3 System Integration

In the system integration phase, the routing system is set to operational use. We identified three major barriers for adoption in this phase.

  • S.1—Inability to invest into a completely new system. The system integration requires a prohibiting investment into a new system as a necessary supporting system is required before the vehicle routing system can be utilized.

  • S.2—Inability to integrate to existing systems. The system integration to existing systems cannot be performed due to lack of resources or knowledge.

  • S.3—Inability to propagate changes to the system from the operational environment. In practice, the operating environment of the enterprise changes frequently, and any planning tool needs to accommodate those changes. Examples include opening a new terminal and changing the cost structure of the transportation. The inability to incorporate these changes is a major concern as this is a hidden cost factor to the usefulness of the routing system, which is difficult to evaluate.

5.4 Barriers by Case

After identifying barriers for deployment, we identified the cases in where the barriers exist. The objective is to understand the implications of the barriers to different types of enterprises. The identified barriers by case are given in Table 31.1.

Table 31.1 Barriers by case
Full size table

We can make several observations from the cases. First, in all cases, there is a realized barrier, and most of the cases have at least two active barriers. Most of the barriers are in the data integration phase, but almost all cases have also identified a barrier in the system integration. Process integration has the most variability between cases, and this may prove to be an interesting observation, although at this stage of the research it has to be yet verified.

On the data integration phase, only one case had no digital data available (D.1), and most data integration issues are related to resources, mainly vehicles (D.4), which are easier to generate than task data, as the data does not change frequently. Relatively few cases identified geographical information (D.5), cost structure (D.6), or existing data (D.7–D.9) as a barrier for data integration. On the process integration phase the identified potential problems relate most frequently decrease in customer satisfaction (P.3). In mission critical environments, the inability to trust the optimization results (P.6) was also identified as a possible barrier. As can be seen, the system integration has one major obstacle—inability to invest into completely new system in order to obtain a routing system (S.2)—in many of the cases. Note also that at this stage of the research, we have not been able to evaluate the change requirements during operational use (S.3).

5.5 Implications for Routing Models and Algorithms

From a data integration perspective, the most direct implication is the need for the algorithms to be able to accommodate manual changes by the user. This interactivity can help to adapt the system in situations where some of the data is not available or cannot be formalized to the system. From the modeling viewpoint, this means the ability to accept custom constraints during potentially interactive optimization.

From a process integration perspective, the ability to automatically select the algorithm parameters robustly to meet the differing needs of the different cases, is implied by the heterogeneity of the processes in the studied cases. This includes the ability to accommodate open planning in a continuous fashion, select algorithm parameters according to the optimization need and availability of the computational budget. In addition, the support for interactively performing manual changes, adjusting parameters and modifying constraints are likely to increase the planners’ confidence in the produced plans.

From a system integration perspective, the main barrier in the studied cases is the inability to invest into a completely new system, which implies that a complementary subsystem or a service may be needed. This, in turn, implies a need for a case-specific routing system. However, scalability would require a generic routing system. To reconcile these requirements in the current context, we suggest using an optimization system that (1) uses an automatically adapting, e.g., hyper heuristic solution methodology and (2) complements the existing systems as a separate service.

6 Conclusions and Further Research

In this paper, we addressed the deployment of the vehicle routing problem optimization into operational use. We have suggested that the deployment of optimization to the SMEs, or the “long tail” of operators would yield large-scale benefits to society.

We argue, based on the preliminary findings in this study, that the self-adaptation and interactivity of the optimization methodology is necessary, not only from the viewpoint of the optimization results, but also that of large-scale system deployment and change management. In this light, priority should be given to methods that are capable of adapting to wide array of optimization problems, such as hyper heuristic solutions that combine the methodology from efficient metaheuristic components, instead of methods that improve a narrow set of results.

Although we are still at the early stage of the study, a number of patterns have emerged on the deployment of the optimization solutions. We certainly do not have solutions for each of the identified barriers, but we nevertheless feel that publishing the preliminary findings is beneficial for other researchers struggling to increase the adoption of routing systems. The next step of the study will be evaluation of the process after a large enough sample of operational use has been collected. In practice, we should verify that the VRP modeling and solution methodology approaches proposed here lower the identified barriers.

In addition, further studies are required especially in automation of the configuration selection and tuning from the viewpoint of the deployment process. This may have implications to the qualities required from optimization methods, which should be critically evaluated in the future. From the modeling viewpoint, interactive approaches may provide to be a fruitful direction, especially when formal data is not properly available. One option is to examine if it is possible to deduce and suggest missing constraints from the manual changes the users make to the solutions frequently.