Article Preview
TopIntroduction
Vehicle Routing Problem (VRP) has many obvious applications in real industries. On the other side, applying the computer optimization programs can give savings of 5% to a company (Hasle, Lie, & Quak, 2007). As transportation is usually a significant component of the product cost (Rodrigue, Comtois, & Slack, 2016), the transportation section makes up about 10% of the EU's GDP. Consequently, any savings created by the VRP can lead to the efficiently in the transportation system (Hasle et al., 2007). An appropriate planning for vehicles routing can also lead to avoiding delivery delays and increasing customer satisfaction. It also can save fuel costs and environmentally related issues. The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimized. This cost may be monetary, distance or otherwise (P Toth & Vigo, 2002). The road network can be described using a graph where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type (Toth & Vigo, 2002).
Small package shipping (SPS) is a fast-growing market strongly driven by the expanding e-commerce sector. Besides the highly competitive market situation, rising fuel and labor costs constantly decrease the players’ profit margins per delivered package. In general, SPS companies perform last-mile deliveries from a set of local depots (Zhong, Hall, & Dessouky, 2007) and the associated pickup and delivery costs are estimated to amount to 35-60% of the total transportation costs (Wasner & Zäpfel, 2004). To render their local pickup and delivery operations profitable and to gain advantage over their competitors, SPS companies pay more and more attention to effective workforce management practices (Smilowitz, Nowak, & Jiang, 2013). An effective utilization of the drivers can be achieved by employing drivers to serve the customers and regions that they are most familiar with them. For example, experienced drivers use shortcuts, know about traffic light intervals, anticipate road or traffic problems, find parking space more easily and know alternative delivery possibilities in case a customer is absent, such that it can lead to reduced travel and service times. In addition, a high service consistency is achieved, i.e., customers are often served by the same driver, leading to increased customer satisfaction, and a stronger bond between company and customers.
To effectively manage local delivery tasks, operations research techniques can be applied, where route planning is generally represented as vehicle-routing problem (VRP) (Paolo Toth & Vigo, 2014). Because customers with time-definite delivery requirements are very common in the SPS sector and constitute up to 60% of the total delivery volume (Campbell & Thomas, 2009), the VRP with time windows (VRPT) lies at the heart of the local delivery operations of an SPS company. It incorporates the most important practical constraints, namely a limited freight capacity of the vehicles and the requirement that each customer can only be visited within a given time window (Desaulniers, Madsen, & Ropke, 2014). To be more precise, the VRPT calls for the determination of a cost-minimal set of routes carried out by a set of identical vehicles located at a single depot. Each route starts and ends at the depot within a given scheduling horizon and the cumulative demand of the customers visited on a route does not exceed vehicle capacity. Each customer is served by exactly one vehicle within its given time window. The VRPTW is an NP-hard problem of which only small to medium-sized instances can be solved within acceptable computation times by means of exact solution methods (Baldacci, Mingozzi, & Roberti, 2012).