This article was automatically translated from the original Turkish version.

Vehicle Routing Problem

+2 More

Subject Headings

Vehicle Routing Problem (VRP)Green LogisticsSustainable TransportationDistribution Optimization

Purpose

Reduction of logistics costs through the determination of optimal distribution routes and reduction of environmental impacts (CO₂ emissions)

Key Concepts

Vehicle RoutingOptimizationCarbon Emission

In an environment where competition is increasingly intensifying, businesses must develop unique strategies that distinguish them from their competitors in order to succeed and sustain their existence over the long term. Research has shown that logistics costs in businesses can account for up to 30 percent of total sales. As the share of transportation costs within overall expenses continues to grow, logistics activities have come to the forefront. Companies aim to implement low-cost strategies by minimizing costs associated with transportation, storage, and distribution processes. The vehicle routing problem, which ranks first among distribution and transportation challenges, is applied in many fields involving the allocation of people and goods. The vehicle routing problem provides solution methods for numerous daily challenges such as airline companies, courier services, gasoline collection and distribution, waste collection and storage, product distribution from central warehouses to sales centers, and the movement of raw materials and various goods between factories.

Vehicle Routing Problem (VRP)

The Vehicle Routing Problem (VRP) was first defined in the literature in 1959 by G. Dantzig and J. Ramser in their paper titled “The Truck Dispatching Problem.” The first mathematical model of the problem was also established in this study. VRP involves planning the most efficient distribution and collection routes for vehicles dispatched from one or more depots to geographically dispersed locations. The objective in vehicle routing problems is to find the optimal route with the least cost and in the shortest possible time. As a frequently encountered problem in logistics and distribution sectors, the vehicle routing problem requires different constraints depending on the industry in which it is applied and the specific goal of the problem. These variations have led to the emergence of various types of vehicle routing problems.

Mathematical Model of the Vehicle Routing Problem

The mathematical model of the vehicle routing problem is used to construct the optimal route. The objective function aims to minimize the total route distance. Constraints ensure the generation of feasible solutions by considering important factors such as customer demands, vehicle capacity, and number of visits. The classical mathematical model of VRP is expressed as follows.

Parameters:

Q = vehicle capacity,

N = number of customers,

qi = demand quantity of customer i (i > 0),

dij = distance between customer i and customer j,

Variables:

Xij={1,0,eg˘er arac¸ i mu¨s¸terisinden j mu¨s¸terisine gidiyorsaaksi takdirde

i=j,i,j∈{0,…,N}ve 0 ana depo

Objective Function:

minZ=∑i=0N∑j=0j=iNdijxij

Constraints:

∑i=1i=jNxij=1,∀j∈{1,…,N}

∑j=1j=iNxij=1,∀i∈{1,…,N}

∑i=0N∑j=0j=iN(xij+xji)≤1,

∑i=1N∑j=0j=iNxij≤Q

Types of the Vehicle Routing Problem

The vehicle routing problem is an optimization problem arising during distribution and collection processes. To obtain a good solution, the problem must be clearly defined. The problem may require different constraints to achieve an optimal solution, and these constraints may vary depending on the industry in which the problem occurs. For example, considering a courier distribution company, vehicles loaded at the depot for delivery have a specific capacity. In addition to the capacity constraint, to ensure customer satisfaction, parcels must be delivered on time. This presents us with a vehicle routing problem with both capacity and time constraints. Generally, the main types of vehicle routing problems include capacitated, distance-constrained, pick-up and delivery, split delivery, and time-window variants.

Solution Methods for the Vehicle Routing Problem

The solution to the vehicle routing problem aims to balance resource supply with customer demand while minimizing the total cost of transportation from the depot to customers, thereby determining optimal delivery routes. Numerous methods have been developed in the literature for solving vehicle routing problems. These methods are categorized into exact and heuristic approaches based on their ability to reach optimal solutions. If a method yields the optimal route, it is classified as an exact method; however, finding optimal solutions to complex, multi-variable problems using exact methods is often very difficult. As the number of constraints increases, solving the problem becomes even more challenging. Therefore, heuristic solution methods have been developed, enabling faster solutions without the need to test all possible combinations. Heuristic solution methods are divided into two main groups: classical heuristics and metaheuristics. The goal of using heuristic or metaheuristic methods is to generate values as close as possible to the optimal solution. Many metaheuristic methods are algorithms inspired by natural phenomena.

Evaluation

One of the greatest threats facing the world as its population grows and industrializes is air pollution. Air pollution constitutes a major ecological threat to the future of our planet. Meeting energy demands through fossil fuel consumption leads to the emission of harmful gases into the atmosphere. These harmful gases, known as greenhouse gases, contribute to air pollution, global warming, and ecological imbalance. Some greenhouse gases include carbon dioxide (CO2), methane (CH4), nitrous oxide (N2O), and ozone (O3). The most significant of these is carbon dioxide (CO2), which accounts for approximately 80 percent of harmful emissions from fossil fuel consumption. One of the largest contributors to CO2 emissions is the industrial sector, which strives to meet the demands and needs of today’s world. Industry accounts for 22 percent of total global CO2 emissions. The distribution sector contributes 20 percent to total CO2 emissions. The significant contribution of the distribution sector to CO2 emissions has played a key role in the emergence of the concept of green logistics. Green logistics aims to minimize carbon dioxide emissions caused by logistics activities. When optimizing vehicle emissions, the use of electric vehicles should be expanded, and optimal delivery routes should be established.

Improvements in the delivery process directly affect the operational capability of logistics and supply chain processes. These improvements help reduce transportation costs and fuel consumption, shorten delivery times, and ensure timely deliveries. This increases customer satisfaction and strengthens customer loyalty. Higher customer satisfaction enhances the competitiveness of supermarket chains. Efficient use of vehicle capacity reduces idle vehicle costs and improves the efficiency of logistics operations. Enhanced vehicle routing strategies reduce traffic congestion and atmospheric emissions, ensuring sustainable fulfillment of customer demands.

Author Information

AuthorEbrar AslantürkDecember 8, 2025 at 12:43 PM

Discussions

No Discussion Added Yet

Start discussion for "Vehicle Routing Problem" article

View Discussions

Vehicle Routing Problem (VRP)
- Mathematical Model of the Vehicle Routing Problem
- Types of the Vehicle Routing Problem
- Solution Methods for the Vehicle Routing Problem
- Evaluation