A Discrete Firefly Algorithm to Solve a Rich Vehicle Routing Problem Modelling a Newspaper Distribution System with Recycling Policy

1 Introduction

• The newspaper distributor’s planning includes recycling, separate town or city units, time-varying travel costs, and prohibited streets.The model is intended to apply to companies with similar characteristics.Source: §1 · p. 2
• The Newspaper Distribution System with Recycling Policy is modeled as an asymmetric, clustered rich vehicle routing problem with simultaneous pickup and delivery, variable costs, and forbidden paths.The paper frames rich vehicle routing problems as routing problems with multiple constraints and complex formulations.Source: §1 · p. 2
• Because firefly algorithms had not been applied to rich vehicle routing problems, the paper develops a discrete firefly algorithm for the proposed problem.The introduction identifies the Hamming-distance measure and evolution-strategy-based movement as features of the DFA.Source: §1 · p. 3
• The study proposes a 15-instance benchmark based on real geographic locations and presents this as the first rich vehicle routing formulation of this newspaper distribution problem.Source: §1 · p. 3
• The DFA is compared with an evolutionary algorithm and an evolutionary simulated annealing algorithm.Source: §1 · p. 4

2 Newspapers Distribution with Recycling Policy

• Each vehicle entering a town or city must serve all customers there, and it cannot enter if its capacity is insufficient for the whole cluster.Source: §2 · p. 4
• Vehicles deliver newspapers and collect those left unsold the previous day, while routes account for higher travel costs during 8:00–10:00 peak hours and prohibited roads.The service period is 6:00–15:00.Source: §2 · p. 4
• Earlier newspaper-delivery studies used two-stage approaches, including separating delivery-plan creation from solving a vehicle routing problem.Source: §2 · p. 4
• The paper presents variable travel times, forbidden paths, and recycling as novelties for newspaper distribution, and its approach solves the problem in one phase rather than two.The text states that one-phase solving can considerably reduce runtime and computational effort.Source: §2 · p. 5

3.1 General description of the problem

• Each route has asymmetric travel costs, serves town or city clusters as indivisible units, and may combine newspaper delivery with collection.Customers requesting collection only are excluded; customers request delivery, and some also request collection.Source: §3.1 · pp. 5–6
• Travel costs are higher during the 8:00–10:00 peak period, and designated arcs cannot be used.The modeled planning schedule runs from 6:00 to 15:00.Source: §3.1 · p. 6
• The AC-VRP-SPDVCFP minimizes the total cost of a set of routes while respecting delivery and collection nodes, vehicle capacity, clusters, and forbidden paths.The combination of constraints makes generating feasible solutions and successors complex.Source: §3.1 · p. 6

3.2 Mathematical description of the problem

• The mathematical model represents nodes as vertices and travel links as arcs, with asymmetric costs and infinite cost assigned to forbidden arcs.It assigns each customer delivery and pickup demands and represents routes, cluster entry, and carried pickup and delivery flows with decision variables.Source: §3.2 · pp. 6–7
• The formulation’s constraints enforce single visits, balanced depot departures and returns, route flow, demand fulfillment, vehicle capacity, permitted arcs, and one vehicle per cluster.Source: §3.2 · pp. 8–9

4.1 Classic Firefly Algorithm

• The classic firefly algorithm attracts less bright fireflies toward brighter ones, with attraction decreasing as distance increases; the brightest firefly moves randomly.For minimization, brightness can be proportional to the reciprocal of the objective value.Source: §4.1 · p. 9

4.2 The proposed Discrete Firefly Algorithm

• The DFA represents each firefly as a feasible AC-VRP-SPDVCFP solution and makes lower-cost solutions more attractive in this minimization problem.The paper sets the light-absorption parameter γ to 0.95.Source: §4.2 · p. 10
• The DFA measures distance by summing Hamming distances across clusters and uses an insertion function that relocates a node within its cluster while respecting capacity.The move length is sampled between 2 and rij·γ^g; evolution strategies generate n potential successors and select the best move.Source: §4.2 · pp. 10–11
• The algorithm initializes and evaluates fireflies, repeatedly moves them toward brighter solutions, evaluates and ranks them, and stops at its termination criterion.Source: §4.2 · p. 11

5.1 The proposed benchmark for the VRP

• The benchmark varies forbidden paths by cluster, and its instance descriptions distinguish cluster selections and customer groupings.Source: §5.1 · p. 13, Table 1 · p. 14
• The benchmark contains 15 instances, and its construction assigns asymmetric travel costs that increase during peak periods; travel time is set equal to travel cost in seconds.Source: §5.1 · p. 13, §5.2 · p. 14

5.2 Results

• All 15 instances were run 20 times, and the DFA, EA, and ESA were compared using similar operators and parameters where possible.Source: §5.2 · pp. 14–15
• A four-version, four-instance population-size study found a slight quality improvement as population increased, alongside a significant runtime increase; DFA100 was selected as the balance.Source: Table 3 · p. 15, §5.2 · pp. 15–16

5.3 Analysis and Discussion

• DFA outperformed ESA on 13/15 instances (86.66%) and EA on 14/15 (93.33%), and found the best solution on 12/15 (80%).Source: Table 4 · p. 16, §5.3 · p. 16, Table 5 · p. 17
• DFA had lower result standard deviation than the other methods in 12 of 15 instances, indicating a narrower range of solution quality across runs.Source: §5.3 · p. 17
• DFA and EA had similar execution times, while ESA was faster; the authors interpret DFA’s longer convergence as greater exploration than ESA and better exploitation than EA.Source: §5.3 · p. 17
• Friedman’s test found significant differences among the three algorithms (statistic 17.73; p-value 0.000141), and Holm’s test found DFA significantly better than both baselines at 95% confidence.Source: Table 6 · p. 18, Table 7 · p. 18, §5.3 · p. 18

• The newspaper distribution problem is modeled as an asymmetric, clustered routing problem with simultaneous pickups and deliveries, variable costs, and forbidden paths.Source: §6 · p. 18
• The DFA outperformed the evolutionary algorithm and evolutionary simulated annealing.Source: §6 · p. 19
• The study presents this problem as new to the literature, develops a 15-instance benchmark using real-world locations, and applies a firefly algorithm to a rich vehicle routing problem for the first time.Source: §6 · p. 19
• Future work includes applying the DFA to other transportation and logistics problems and studying its parameterization and time complexity, which this study did not address.The stated primary objective was to present the NDSRP model and demonstrate DFA performance on an R-VRP.Source: §6 · p. 19