Vehicle routing problems (VRP) involve designing optimal delivery or collection routes from one or several depots to a set of geographically scattered customers, subject to various constraints. The primary objective is to minimize the total travel cost, which may represent distance, time, or number of vehicles used. Each customer is visited exactly once by a single vehicle, and all routes start and end at a depot.
Common constraints in VRP variants include:
- Capacity limit: Each vehicle has a maximum load it can carry.
- Service time: Total route duration must not exceed a maximum working time.
- Time windows: Service at each customer must begin within a specified time interval (soft or hard constraints).
- Fleet size: The number of available vehicles is limited.
- Demand fulfillment: Each customer's demand must be fully satisfied.
- Route distance limit: Maximum travel distance per vehicle.
- Precedence constraints: Some customers must be visited before others.
Solution approaches range from exact methods (e.g., mixed-integer linear programming, branch-and-bound) to heuristics (savings algorithm, insertion heuristics) and metaheuristics (simulated annealing, genetic algorithms, tabu search, ant colony optimization). Hybrid methods combining multiple techniques often yield high-quality solutions for large-scale instances.
Genetic Algorithm Framework
A genetic algorithm (GA) is an evolutionary optimization technique that iteratively evolves a population of candidate solutions using selection, crossover, and mutation operators. For VRP, GA provides flexibility to handle complex constraints and multiple objectives.
Chromosome Encoding
The proposed encoding uses a triple-chromosome representation:
- Customer permutation: Sequence of customer indices representing the order of visits.
- Vehicle segmentation: A list of cut points that partition the customer sequence among vehicles.
- Depot assignment: A vector indicating which depot each vehicle is assigned to.
For example, with 8 customers (indices 0–7), 3 vehicles, and 2 depots (indices 8 and 9), a individual might be encoded as:
[0, 1, 2, 3, 4, 5, 6, 7, 3, 5, 8, 9, 8]
Where:
[0,1,2,3,4,5,6,7]is the customer permutation.[3,5]defines vehicle coverage: Vehicle 1 covers positions 0–2 (cusotmers 0,1,2), Vehicle 2 covers positions 3–4 (customers 3,4), Vehicle 3 covers positions 5–7 (customers 5,6,7).[8,9,8]assigns Vehicle 1 to Depot 8, Vehicle 2 to Depot 9, Vehicle 3 to Depot 8.
Decoded routes:
Route 1: [8, 0, 1, 2, 8]
Route 2: [9, 3, 4, 9]
Route 3: [8, 5, 6, 7, 8]
Individual Generation
def generate_individual(self):
# Random permutation of customers
perm = list(range(self.vrp.customer_num))
random.shuffle(perm)
# Random segmentation points
segments = []
remaining = self.vrp.customer_num
for v in range(self.vehicle_num - 1):
max_split = remaining - (self.vehicle_num - v - 1)
split = randint(1, max_split) if max_split > 0 else 1
segments.append(split)
remaining -= split
segments.append(remaining)
# Random depot assignment for each vehicle
depots = []
for _ in range(self.vehicle_num):
depots.append(choice(self.vrp.depot_list))
return Chromosome(perm, segments, depots)
The GA then iteratively evaluates fitness, selects parents, applies crossover and mutation operators. The fitness function incorporates penalty terms for constraint violations (e.g., overload, time window breach) to guide the search towards feasible solutions.
Crossover combines two parent chromosomes to produce offspring, typically using order-based crossover for the permutation part and single-point crossover for segmentation and depot lists. Mutation introduces random changes, such as swapping two customers in the permutation, adjusting a segment boundary, or reassigning a vehicle to a different depot.
This framework can be easily extended by integrating local search heuristics (e.g., 2-opt, simulated annealing) to form hybrid algorithms that improve convergence and solution quality.