Abstract

Effective household waste management in developing cities requires optimization approaches adapted to local constraints. This article proposes a methodological framework for bi-weekly collection planning in Conakry, where the territory is divided into two sectors serviced on different days. The study aims to reconcile two often conflicting objectives: minimizing operational costs (total distance traveled) and maximizing operational regularity between early-week and weekend cycles. Regularity is defined as the similarity of operational characteristics (number of vehicles, distances, schedules) between the two sets of routes, aiming to ensure predictable service for users and stable working conditions for collection teams. Six construction heuristics are designed according to different generative logics and compared on Solomon instances adapted to the specifics of Conakry. The results reveal a fundamental trade-off: the most economically effective method (independent route construction) generates the lowest regularity, while the method optimizing regularity leads to significantly higher costs. Hybrid methods offer intermediate trade-offs whose performance varies according to the geographical configuration of collection points and the severity of time constraints. This research provides Conakry’s decision-makers with a decision-making framework for choosing a planning strategy aligned with their operational and financial priorities.

Keywords

Waste Logistics, Multi-Objective Optimization, Route Regularity, Heuristic Methods, Vehicle Routing Problem with Time Windows, Conakry

Share and Cite:

1. Introduction

Rapid urbanization in developing countries exacerbates the challenges of municipal solid waste management, with direct implications for public health, environmental quality, and the economic viability of cities [1] [2]. Collection, often the highest cost stage of the management chain, represents a crucial leverage point for system improvement [3]. In Conakry, the capital of Guinea, the National Agency for Sanitation and Public Cleanliness (ANASP-CONAG) operates in a context of limited resources facing increasing waste production, making complete collection in a single day impossible [4] [5].

Operations research has for several decades offered models for optimizing collection routes, mainly based on the Vehicle Routing Problem (VRP) and its variants [6] [7]. Notable applications have demonstrated their potential in various urban contexts [8]-[10]. However, the dominant literature has traditionally focused on minimizing direct costs (distance, time, number of vehicles), often neglecting qualitative dimensions essential to the sustainability and social acceptability of the service, such as its regularity and predictability [11] [12].

This study positions itself in this space by formalizing a bi-objective optimization problem for weekly collection in Conakry. The territory is organized into two fixed sectors, generating two collection cycles per week. Beyond the classic objective of cost minimization, we introduce and formally model a second objective: weekly operational regularity. This concept, which goes beyond the simple notion of frequency, is defined as the minimization of the gaps between the characteristics of the early-week ($S_{start}$ ) and weekend ($S_{end}$ ) routes. It is analyzed through a multidimensional prism integrating resource regularity (fleet), service regularity (schedules for the user) and work regularity (load and itinerary for the teams).

To solve this complex problem, we design and compare six original route construction heuristics, evaluated on Solomon benchmark instances adapted to reflect the prevailing operational hypothesis in Conakry, where the majority of points are collected twice a week. By illuminating the trade-offs between economic efficiency and service quality, this research aims to provide Conakry’s managers, and those in similar urban contexts, with informed planning strategies, where the choice of method will depend on the desired trade-off between financial performance and operational reliability.

2. Problem Modeling

2.1. General Framework and Mathematical Formalism

The problem is modeled as a Vehicle Routing Problem with Time Windows (VRPTW) defined on a directed graph $G=\left(V,A\right)$ , where:

• $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ is the set of vertices ($v_0$ is the depot, the others are collection points),

• $A=\left\{\left(v_i,v_j\right):v_i,v_j\in V,i\ne j\right\}$ is the set of arcs.

Parameters:

• $K=\left\{1,\cdots ,m\right\}$ : set of homogeneous vehicles with capacity $Q$ .

• $q_i$ : quantity to collect at point $v_i$ .

• $d_{ij}$ : distance between $v_i$ and $v_j$ .

• $\left[a_i,b_i\right]$ : time window for service at point $v_i$ .

• $t_i$ : service time at point $v_i$ .

• $t_{ij}$ : travel time between $v_i$ and $v_j$ .

• $M$ : Sufficiently large positive constant.

Decision variables:

• $x_{ij}^k\in \left\{0,1\right\}$ : Equal to 1 if arc $\left(v_i,v_j\right)$ is used by vehicle $k$ .

• $y_i^k\in \left\{0,1\right\}$ : Equal to 1 if point $v_i$ is served by vehicle $k$ .

• $u_i^k\ge 0$ : continuous variable indicating the arrival of vehicle $k$ at point $v_i$ .

2.2. Specificities of the Conakry Context: Collection Frequencies

The current organization divides the city into two fixed geographical zones, each collected on specific days, creating two cycles per week. Collection points ($v_i$ ) are characterized by their frequency:

• $Z_{c_1}$ : Points collected once a week.

• $Z_{c_2}$ : Points collected twice a week.

Operational hypothesis: In accordance with field observations and ANASP-CONAG constraints, we assume that $\left|Z_{c_2}\right|>\left|Z_{c_1}\right|$ . The points of $Z_{c_1}$ are all assigned to the early-week cycle, while those of $Z_{c_2}$ must be visited both early-week ($S_{start}$ ) and weekend ($S_{end}$ ). This hypothesis leads to two related but distinct VRPTW problems (Figure 1):

1) $VRPT{W}_{start}$ : Serves the set $S_{start}=Z_{c_1}\cup Z_{c_2}$

2) $VRPT{W}_{end}$ : Serves only the set $S_{end}=Z_{c_2}$ , with generally reduced quantities $q_i$ .

Figure 1. Diagram representing the collection if $\left|Z_{c_2}\right|>\left|Z_{c_1}\right|$ .

2.3. Formulation of Objectives

The model pursues two main objectives.

Objective 1: Cost minimization.

The operational cost is mainly proportional to the total distance traveled by the fleet over the week. We seek to minimize the sum of the distances of the two cycles:

$\min C_{total}={\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in V}{\displaystyle \sum _{k\in K}{d}_{ij}\left(x_{ij}^{k,start}+x_{ij}^{k,end}\right)}}}$ (1)

where $x_{ij}^{k,start}$ and $x_{ij}^{k,end}$ are the variables for the early and end cycles respectively.

Objective 2: Maximization of operational regularity.

Regularity is defined as the similarity between $S_{start}$ and $S_{end}$ . It is measured by a set of deviation indicators to minimize:

1) Global resource regularity:

$\Delta M=\left|M_{start}-M_{end}\right|$ (2)

$\Delta D=\left|D_{start}-D_{end}\right|$ (3)

$\Delta T=\left|{\displaystyle {\sum }_{i,j,k}\left(t_{ij}+t_i\right)x_{ij}^{k,start}}-{\displaystyle {\sum }_{i,j,k}\left(t_{ij}+t_i\right)x_{ij}^{k,end}}\right|$ (4)

where $M_{start}$ , $M_{end}$ are the numbers of vehicles used.

2) Service regularity for the user: Measured by the stability of passing times.

$\Delta H={\displaystyle {\sum }_{i\in Z_{c_2}}{\displaystyle {\sum }_k\left|u_i^{k,start}-u_i^{k,end}\right|}}$ (5)

3) Work condition regularity: Evaluated by the similarity of routes assigned to each vehicle $k$ .

$\Delta D_{emp}^k={\displaystyle {\sum }_i\left|{\displaystyle {\sum }_{i,j,k}\left(d_{ij}\right)x_{ij}^{k,start}}-{\displaystyle {\sum }_{i,j,k}\left(d_{ij}\right)x_{ij}^{k,end}}\right|}$ (6)

$\Delta V_i{s}_{emp}^k=\left|{\displaystyle {\sum }_i{y}_i^{k,start}}-{\displaystyle {\sum }_i{y}_i^{k,end}}\right|$ (7)

The minimization of the sum of these deviations over all vehicles constitutes the regularity objective.

2.4. Model Constraints

The classic VRPTW constraints apply separately to each cycle ($S_{start}$ et $S_{end}$ ), including: vehicle capacity constraints, flow constraints (each point is served once), subtour elimination constraints, and time window compliance constraints [14]. A link constraint specifies that any point $v_i\in Z_{c_2}$ must be present in both tour sets.

3. Proposed Heuristic Methods

Solving this bi-objective problem exactly is complex. We propose six construction heuristics that integrate the concern for regularity differently.

Pre-processing: Basic construction. All methods use a common procedure to generate an initial set of routes for a given VRPTW problem. This procedure, noted Construire_Tours (VRPTW), implements Solomon’s parallel insertion heuristic [13] followed by local descent phases (String Exchange and Or-opt) to improve the solution.

3.1. Group A: Initial Construction on $S_{start}$

These methods first generate the early-week routes, then derive the weekend ones.

Method A1 (Progressive deletion) (Figure 2).

1) Construction: $S_{start}\leftarrow$ Construction_Tours (VRPTW_start)

2) Initialization: $S_{end}$ is initialized as an exact copy of $S_{start}$ .

3) Deletion under constraints: For each point $v_i\in Z_{c_1}$ , deletion is attempted. The point is removed from its tour in $S_{end}$ only if the new route remains feasible (respect of time windows and capacity). If deletion creates infeasibility, the point is kept and marked as non-deletable.

Figure 2. Deletion of nodes collected in c₁.

4) Re-optimization: Once all feasible deletions are performed, the Or-opt method is applied to $S_{end}$ .

Method A2 (Guided random deletion) (Figure 3).

1) Construction: $S_{start}\leftarrow$ Construire_Tours (VRPTW_start).

2) Initialization: $S_{end}$ est une copie de $S_{start}$ .

3) Probabilistic selection: At each iteration, a route $R$ from $S_{end}$ is selected with a probability

$p\left(R\right)=\frac{\frac{1}{\left|R\right|}}{{{\displaystyle \sum }}_{r\in S_{fin}}\frac{1}{\left|r\right|}}$ (8)

where $\left|R\right|$ is the number of points in route $R$ .

Figure 3. Transfer of nodes to remaining tours.

4) Deletion and verification: A point v_i is chosen randomly from R for deletion. Deletion is performed only if it preserves the feasibility of the modified route.

5) Stop: The process iterates until all points of $Z_{c_1}$ have been deleted or no feasible deletion is possible.

6) Re-optimization: Apply Or-opt to $S_{end}$ .

Method A3 (Probabilistic transfer) (Figure 4).

1) Construction: $S_{start}\leftarrow$ Construire_Tournées (VRPTW_start).

2) Initialization: $S_{end}$ is a copy of $S_{start}$ .

3) Source tour selection: A tour $R_{source}$ is selected with the probability

$p_{source}\left(R\right)=\frac{1-\frac{\left|R\right|}{\left(1-\frac{\left|r\right|}{\max \left|r\right|}\right)}}{{{\displaystyle \sum }}_{r\in S_{fin}}\left(1-\frac{\left|r\right|}{\max \left|r\right|}\right)}$ (9)

Note: This formula appears corrupted in the original. The intended meaning is selection probability inversely proportional to route size relative to the maximum.

4) Point and target route selection: A point $v_i$ is chosen randomly from $R_{source}$ . A target route $R_{target}$ (different from $R_{source}$ ) is selected with a probability proportional to its remaining capacity:

$p_{target}\left(R\right)=\frac{Q-load\left(R\right)}{{{\displaystyle \sum }}_{r\ne R_{source}}\left(Q-load\left(r\right)\right)}$ , (10)

where $load\left(R\right)$ is the current load of tour $R$ .

5) Insertion: Point $v_i$ is inserted into $R_{cible}$ at the position that minimizes the increase in total route distance, subject to constraint compliance.

6) Deletion: If insertion is successful, $v_i$ is deleted from $R_{source}$ . The method iterates until all points of $Z_{c_1}$ have been transferred.

7) Re-optimization: Apply Or-opt to $S_{end}$ .

Figure 4. Moving a node in method 3.

3.2. Group B: Initial Construction on $S_{end}$

These methods start from the weekend routes to construct the early-week ones.

Method B1 (Addition of dedicated tours) (Figure 5).

1) Construction: $S_{start}\leftarrow$ Construire_Tournées (VRPTW_start).

2) Initialization: $S_{start}$ is initialized as a copy of $S_{end}$ .

3) Creation of an auxiliary tour: All points of $Z_{c_1}$ are grouped into one or several new routes, without initial capacity consideration, to form a set of auxiliary routes $aux$ .

4) Insertion with feasibility check: For each point $v_i$ in each route of $aux$ , we attempt to insert it into an existing route of $S_{start}$ at the position that minimizes the increase in total distance, only if this insertion respects the constraints.

5) Deletion of empty auxiliary tours: After successful insertion, empty auxiliary routes are deleted.

6) Re-optimization: Apply Or-opt to $S_{start}$ .

Figure 5. Constructing a tour with nodes in c₁.

Figure 6. Method 5 for $Z_{c_1}<Z_{c_2}$ .

Method B2 (Proximity-guided insertion) (Figure 6).

1) Construction: $S_{end}\leftarrow$ Construire_Tours (VRPTW_end).

2) Initialization: $S_{start}$ is a copy of $S_{end}$ .

3) Seed identification: For each point $v_i\in Z_{c_1}$ , identify the closest point (minimum Euclidean distance) $v_j\in Z_{c_2}$ . This point $v_j$ serves as a “seed”.

4) Creation of new tours: For each seed $v_j$ , if it is not already in a dedicated route, create a new route in $S_{start}$ starting from the depot, visiting $v_j$ , and returning to the depot.

5) Point insertion: Each point $v_i\in Z_{c_1}$ is inserted into the route of $S_{start}$ that contains its associated seed $v_j$ , provided the insertion respects the constraints. Insertion is done at the position that minimizes the increase in total distance

6) Re-optimization: Apply Or-opt to $S_{start}$ .

3.3. Group C: Independent Construction

Method C1 (Separate optimization).

1) Independent construction: $S_{start}\leftarrow$ Construire_Tours (VRPTW_start).

2) Independent construction: $S_{end}\leftarrow$ Construire_Tours (VRPTW_end).

This method deliberately ignores the regularity objective, optimizing each cycle independently. It serves as a benchmark for the minimal cost objective.

3.4. Parameterization and Implementation Details

To ensure reproducibility, we detail here the parameters and rules used.

Procedure: Construire_Tours (VRPTW_end)

Solomon parallel insertion: We use Solomon’s heuristic (1987) with the seed selection rule based on the farthest distance from the depot. The insertion cost function is

$c_1\left(i,u,j\right)=\alpha d_{iu}+\beta d_{uj}-\gamma d_{ij}$ (11)

where $\left(i,j\right)$ is an existing arc and $u$ the node to insert. Parameters are set to $\alpha =1.0$ ; $\beta =1.0$ ; $\gamma =0.5$ . Priority is given to the feasible insertion minimizing the distance increase.

• Local search:

• String Exchange (λ-interchange): We use a neighborhood of type 1-1 (exchange of one node between two routes) and 2-0 (movement of two consecutive nodes). The search stops after 50 iterations without improvement.

• Or-opt: We consider moving sequences of 1, 2, and 3 consecutive nodes. The search stops after 30 iterations without improvement.

Stop rules and probabilistic parameters:

• Methods A2 and A3: The maximum number of iterations is set to 500, or stop if all points of $Z_{c_1}$ have been processed.

• Tie-breaking rules: In case of equality on the cost function (distance), the solution minimizing the total travel time is selected. If equality persists, the solution with the fewest vehicles is chosen.

Execution time:

Experiments were conducted on a computer with an Intel Core i7-11800H processor and 16 GB of RAM. The average execution time per method for a 100-point instance is reported in Table 1.

Table 1. Average execution time (seconds) per method.

4. Numerical Experiments

4.1. Dataset and Adaptation

The methods are evaluated on Solomon’s 100-customer instances [13]. To simulate the bi-weekly context of Conakry, each original instance $I$ is adapted:

1) A subset of points is randomly designated as $Z_{c_1}$ (10%, 20% or 30% of points), the rest forming $Z_{c_2}$ .

2) Two derived instances are created:

• $I_{debut}$ : For $v_i\in Z_{c_1}$ , $q_i\leftarrow q_i\times 1.6$ . For $v_i\in Z_{c_2}$ , $q_i$ unchanged.

• $I_{fin}$ : For $v_i\in Z_{c_1}$ , $q_i\leftarrow 0$ . For $v_i\in Z_{c_2}$ , $q_i\leftarrow q_i\times 0.8$ .

3) Tests cover 56 instances, including geographical types (C: clustered, R: random, RC: mixed) and constraint types (Type 1: tight windows, Type 2: wide windows).

Justification of scale factors: The factors 1.6 (early week) and 0.8 (weekend) are based on empirical data collected by ANASP-CONAG over an 8-week period (January-February 2023) in three communes of Conakry (Kaloum, Dixinn, Matam). The estimation method consisted of weekly sampling of waste volumes per collection point. The average ratio between the volume of the first collection day (Monday/Tuesday) and that of the second (Thursday/Friday) was 1.62 (standard deviation 0.18), justifying the factor 1.6. The factor 0.8 reflects the average reduction observed at the weekend (i.e., 1/1.6 ≈ 0.625), rounded to 0.8 to account for residual variability and a slight systematic underestimation of weighings at the beginning of the week.

4.2. Reference Method: NSGA-II

To contextualize the performance of our heuristics, we implemented the genetic algorithm NSGA-II (Non-dominated Sorting Genetic Algorithm II), a well-established reference method for multi-objective optimization problems [15]. The population was set to 100 individuals, with a crossover rate of 0.9 and a mutation rate of 0.1. The algorithm was run for 200 generations.

4.3. Sensitivity Analysis on Scale Factors

To assess the robustness of our conclusions to the scale factor hypothesis, we conducted a sensitivity analysis. We tested three alternative scenarios on a subset of 18 instances (6 of each type C, R, RC):

• Low Scenario: $q_{start}=q\times 1.3;q_{end}=q\times 0.9$

• Medium (Base) Scenario: $q_{start}=q\times 1.6;q_{end}=q\times 0.8$

• High Scenario: $q_{start}=q\times 2.0;q_{end}=q\times 0.6$

The relative ranking of methods (in terms of cost-regularity trade-off) remained stable across the three scenarios.

4.4. Performance Measures

For each method and instance, we record:

• Total cost $Cos{t}_{total}$ : Sum of distances of $S_{start}$ and $S_{end}$ .

• Composite regularity index: Normalized average of deviations $\Delta M$ , $\Delta D$ , $\Delta H$ , $\Delta D_{emp}$ , $\Delta V_{i{S}_{emp}}$ . A lower value indicates better regularity.

5. Results and Analysis

5.1. Global Analysis of Trade-Offs

Figure 7. Comparison of methods in terms of cost per type of instance.

Figure 1 presents the approximate Pareto front between total cost (normalized x-axis) and regularity index (normalized y-axis) aggregated over all instances. The results clearly confirm the antagonism between the two objectives.

The Method C1 (independent construction) positions itself as the extreme point minimizing cost but maximizing regularity gaps. Conversely, Method B2 (guided insertion) achieves the best regularity at the cost of a significant increase in cost (on average +18% compared to C1). The methods from Groups A and B1 occupy the intermediate space of compromise (Figure 7).

5.2. Performance by Instance Type

Detailed analysis reveals that the relative performance of the methods depends heavily on the instance structure (Figure 8).

• Type 1 instances (tight windows): In this constraining context, Methods A1 and B1 offer the best compromise.

• Type 2 instances (wide windows): The increased flexibility allows Method A2 (random deletion) to shine, offering an excellent balance.

(a)

(b)

(c)

Figure 8. (a) Comparison of methods in terms of overall stability by instance type; (b) Comparison of methods in terms of overall stability by instance type; (c) Comparison of methods in terms of overall stability by instance type.

5.3. Stability of Schedules and Working Conditions

Method B2 is systematically the best for minimizing variations in passing time $\left(\Delta H\right)$ , crucial for user satisfaction, and for ensuring similarity of routes per vehicle $\left(\Delta D_{emp},\Delta V_i{s}_{emp}\right)$ . Method C1 produces the worst results on these indicators (Figure 9).

Figure 9. Comparison of methods in terms of “user” stability by instance type.

5.4. Comparison with the Reference Method NSGA-II

The NSGA-II algorithm was executed on the same set of instances. For a comparable computational budget (time limited to 60 seconds per instance), the extreme solutions of NSGA-II were systematically dominated by the solutions of methods C1 and B2 respectively. For example, the average cost of NSGA-II’s best “low-cost” solution was 7.5% higher than that of C1, and the regularity index of its best “regular” solution was 15% higher (worse) than that of B2 (Figure 10).

(a)

(b)

(c)

Figure 10. (a) Comparison of methods in terms of stability “employees” by instance type; (b) Comparison of methods in terms of stability “employees” by instance type; (c) Comparison of methods in terms of stability “employees” by instance type.

6. Discussion and Management Implications

6.1. Strategic Choice for ANASP-CONAG

The results do not designate a universally “best” method but provide a map for an informed strategic choice:

• Priority “Cost control”: Method C1 should be favored. Its implementation would require accepting operational irregularity and setting up adapted communication towards users and teams.

• Priority “Stable and equitable service”: Method B2 is recommended, particularly in residential areas where predictability is valued. The cost increase should be considered an investment in service quality and social climate.

• Need for a “pragmatic compromise”: Methods A1 (Type 1) or A2 (Type 2) are ideal candidates. They capture a substantial part of the savings from C1 while maintaining acceptable operational regularity, facilitating daily management.

6.2. Implementation Challenges and Model Limits

Transposing these results to the field in Conakry must consider factors not modeled: variable reliability of the vehicle fleet, seasonal impact (rains) on road navigability and travel times, and daily fluctuation of waste volumes. These uncertainties suggest that a method too rigid in its search for regularity (like B2) could be fragile. Conversely, complete irregularity (C1) could be unmanageable. The compromise methods (A1, A2, B1), by their intrinsic flexibility, could offer greater operational robustness.

7. Conclusions

This study formalized and solved a bi-objective optimization problem for waste collection in Conakry, highlighting the fundamental trade-off between economic efficiency and operational regularity. The six proposed heuristics cover a spectrum of solutions, from pure cost minimization to pure maximization of route similarity.

The main contribution is practical: to provide ANASP-CONAG with a quantitative decision-making framework for choosing a planning strategy aligned with its political, financial, and social priorities. The study also shows that performance is contextual, depending on the geographical configuration and time constraints of collection zones.

Research perspectives include the integration of real data from Conakry (GPS, volumes) to refine the model, the incorporation of stochasticity (traffic, breakdowns) to assess method robustness, and the development of an interactive decision support tool allowing planners to visualize and choose in real time among compromise solutions. Such an approach could significantly improve the performance and sustainability of the public waste collection service in the Guinean capital.

Author Contributions

Study conception: O.T., M.D.B., A.T. Protocol and methodology development: O.T., M.S., C.G.H., M.L. Data analysis and interpretation: O.T., M.L., M.D.B., C.G.H. Original manuscript writing: O.T., M.S., M.D.B. Review and editing: B.M.T., B.M., A.T. All authors approved the final version of the manuscript.

Funding

This research work did not benefit from any specific funding from public, commercial, or non-profit agencies.

Acknowledgements

The authors would like to thank the management of ANASP-CONAG for its openness, as well as the neighborhood chiefs of Conakry for their collaboration during the survey phases. They also thank the students of the Department of Mathematics at Gamal Abdel Nasser University for their field assistance.

Conflicts of Interest

The authors declare that they have no financial or personal conflicts of interest that could influence the work reported in this article.

References