Sustainable waste collection optimization

In this repository we provide our personal implementation of the models described in this paper, by Erfan Babaee Tirkolaee, Alireza Goli, Selma Gütmen, Gerhard-Wilhelm Weber, Katarzyna Szwedzka.

In particular, two models are implemented:

• epsilon-constraint method;
• MOSA-MOIWOA (i.e., Multi-Objective Simulated Annealing combined with Multi-Objective Invasive Weed Optimization Algorithm).

Additionally, a comparative study on the two algorithms is provided in this presentation.

Table of contents

• What you will find in this repository
• Requirements
• How to prepare a valid dataset
• How to use the models
• References

What you will find in this repository

• WCO_lib/: library, containing the following modules:
  • dataset.py: classes to generate dataset;
  • evaluate.py: functions to compute objectives and evaluation metrics;
  • models_exact.py: single-objective models for epsilon-constraint solver;
  • models_heuristic.py: various algorithms for MOSA-MOIWOA;
  • mutations.py: functions to perform mutations in MOSA-MOIWOA;
  • params.py: parameter classes for data and algorithms;
  • solve_epsilon.py: epsilon-constraint solver;
  • solve_moiwoa.py: MOSA-MOIWOA solver;
  • subtours.py: functions to handle subtours in MOSA-MOIWOA;
• scripts/: scripts for comparative study;
• tests/: various tests used during development;
• docs/: papers and presentations; in particular contains:
  • Implementation_details.pdf: detailed description of the implementations;
  • Presentation.pdf: presentation of the comparative study;
• requirements.txt: list of required packages to run the code.

Requirements

To use the library you need to have python3 installed on your machine.

The required packages are listed in requirements.txt.

Notice: to use the epsilon-constraint method you need to have a valid gurobi license. Instructions to obtain one can be found here.

If you want to use MOSA-MOIWOA with a non-default configuration, you also need to create a JSON file containing the following parameters:

"N_0" -> int (default: 10)
"MOSA_T_0" -> float (default: 800)
"MOSA_max_iter" -> int (default: 200)
"MOSA_max_non_improving_iter" -> int (default: 10)
"MOSA_alpha" -> float (default: 0.9)
"MOSA_K": -> float (default: 70)
"MOIWOA_S_min" -> float (default: 9)
"MOIWOA_S_max" -> float (default: 200)
"MOIWOA_N_max" -> int (default: 100)
"MOIWOA_max_iter" -> int (default: 300)

How to prepare a valid dataset

A valid dataset directory should contain the following files (with this exact names):

• problem_parameters.json: file containing problem size and scala parameters (see below for more info);
• c.npy
• cv.npy
• d.npy
• G.npy
• t.npy

c, cv, d, G and t refer to the parameters under the same name in the original paper, here saved in binary files.

problem_parameters.json should contain the following parameters:

"num_nodes" -> int
"num_edges" -> int
"num_required_edges" -> int
"num_periods" -> int
"num_vehicles" -> int
"W" -> float
"T_max" -> float
"M" -> int
"theta" -> float
"sigma" -> float
"ul" -> float
"uu" -> float

Refer to the original paper for names reference.

If you don't have a dataset, you can generate a synthetic one by using the function generate_dataset, contained in the dataset.py module of the library.

A method to compute "good parameters" is also available: given a problem size (i.e. a set of values for num_nodes, num_edges, num_required_edges, num_periods and num_vehicles), good values for other parameters in the JSON can be computed using either the function compute_good_parameters or compute_good_parameters_random (the first one is suggested), contained in the dataset.py module of the library. By "good parameters", we mean parameters that allow you to generate (using the functions of the dataset.py module) datasets that have a feasible but not trivial solution (if you are interested in the way this parameters are computed, see the presentation).

How to use the models

1. Clone the repository on your machine:

   $ git clone [email protected]:TommasoTarchi/Waste_collection_optimization.git

2. Place the following lines of code at the beginning of each script using the library:

   import sys
   
   library_path = </path/to/WCO_lib>
   if library_path not in sys.path:
       sys.path.append(library_path)

3. Before running any model make sure you satisfy all requirements listed in this section and have a valid dataset (please take a look at the previous section to correctly generate/prepare your dataset).

4. Depending on the model you want to run, import the needed classes and functions:

   • For epsilon-constraint method, here is the minimal import:

     from WCO_lib.params import ProblemParams
     from WCO_lib.solve_epsilon import EpsilonSolver

   • For MOSA-MOIWOA, here is the minimal import:

     from WCO_lib.params import ProblemParams, MosaMoiwoaSolverParams
     from WCO_lib.solve_moiwoa import MosaMoiwoaSolver

5. Create a ProblemParams object, specifying the path to the dataset:

   problem_params = ProblemParams()
   problem_params.load_from_dir(</path/to/data/directory/>)

6. Depending on which algorithm you want to use, follow the instructions contained in the following sections.

Epsilon-constraint method

7. Create an EpsilonSolver object passing the problem parameters:

   solver = EpsilonSolver(problem_params)

8. Solve the single objective sub-problems:

   solver.solve_single_objectives()

9. Choose the number of epsilons you want to use <num_epsilon>, then compute the epsilon values and solve the multi-objective problem:

   solver.compute_epsilon(<num_epsilon>)
   solver.solve_multi_objective()

10. Retrieve the Pareto solutions:

    pareto_solutions = solver.return_pareto_solutions()

    The returned object is a list of dictionaries, each one representeing a Pareto solution. The keys of the dictionaries correspond to the paper's variable names (x, y, u, LT, UT, WT).

MOSA-MOIWOA

7. Build the graph corresponding to the dataset:

   problem_params.build_graph()

8. Create a MosaMoiwoaSolverParams object, specifying the path to parameters file:

   solver_params = MosaMoiwoaSolverParams()
   solver_params.load_from_file(</path/to/solver/parameters/file>)

   Notice: if you are ok with default parameters, you can avoid creating the parameters file and skip the second line.

9. Create a MosaMoiwoaSolver object passing the problem parameters and the solver parameters:

   solver = MosaMoiwoaSolver(problem_params, solver_params)

10. Generate initial solutions:

    solver.generate_initial_solutions()

11. Refine initial solutions using MOSA:

    solver.apply_MOSA()

12. Run MOIWOA:

    solver.apply_MOIWOA()

13. Retrieve the Pareto solutions:

    pareto_solutions = solver.return_pareto_solutions()

    The returned object is a list of lists, each one representing a Pareto solution (see the implementation details for complete description).

References

• Tirkolaee, E.B., Goli, A., Gütmen, S. et al. A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms. Ann Oper Res 324, 189–214 (2023). https://doi.org/10.1007/s10479-021-04486-2.

• Amine, Khalil, Multiobjective Simulated Annealing: Principles and Algorithm Variants, Advances in Operations Research, 2019, 8134674, 13 pages, 2019. https://doi.org/10.1155/2019/8134674.

• Gurobi Optimizer, developed by Gurobi Optimization, LLC. https://www.gurobi.com.