A Hybrid Approach Based on LP Metric Method and Genetic Algorithm for the Vehicle-Routing Problem with Time Windows, Driver-Specific Times, and Vehicles-Specific Capacities

A Hybrid Approach Based on LP Metric Method and Genetic Algorithm for the Vehicle-Routing Problem with Time Windows, Driver-Specific Times, and Vehicles-Specific Capacities

Ebrahim Asadi-Gangraj, Sina Nayeri
DOI: 10.4018/IJORIS.2018100104
(Individual Articles)
No Current Special Offers


Due to increasing population, increasing number of vehicles as well as environmental pollution, planning vehicles efficiently one of important problems nowadays. This article proposes a Multi-Objective Mixed Integer Programming (MOMIP) model for the vehicle-routing problem with time windows, driver-specific times and vehicles-specific capacities (VRPTDV), a variant of the classical VRPT that uses driver-specific travel and service times and vehicles-specific capacity to model the familiarity of the different drivers with the customers to visit. The first objective function aims to minimize traveled distance and the second objective function minimizing working duration. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, the hybrid approach based on LP metric method and genetic algorithm is proposed to solve the given problem.
Article Preview


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).

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 14: 1 Issue (2023)
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing