Carlo Sulzbach Sartori

Metaheuristic methods to solve pickup and delivery problems with time windows

A matheuristic approach

This research project was developed during my MSc. in Computer Science at UFRGS, under the supervision of Dr. Luciana S. Buriol. We investigated hybrid methods combining metaheuristics and mathematical programing, the so-called matheuristics. Among the approaches we have tried were fix-and-optimize using a two-index formulation of the PDPTW [Furtado et al. 2017] and a Construct, Merge, Solve and Adapt [Blum et al., 2016] method using the same two-index formulation of the problem. Unfortuntely, both methods provided poor performance and were discontinued.

The approach that obtained the best results was a set partitioning method. In this case, we modeled the PDPTW as a set partitioning problem, where each set (column) is a feasible route. The matheuristic then creates a large pool of routes and uses a subset of this pool to create a solution where every customer request is visited exaclty once. Routes were generated by means of an improved version of the state-of-the-art metaheuristic at the time proposed by Curtois et al. (2018) embedded within an Iterated Local Search procedure [Lourenço et al., 2003].

We have published two papers detailing the results of this research:

  1. Sartori, C. S., & Buriol, L. S. (2018). A matheuristic approach to the pickup and delivery problem with time windows. In International Conference on Computational Logistics (pp. 253-267). Springer, Cham.
  2. Sartori, C. S., & Buriol, L. S. (2020). A study on the pickup and delivery problem with time windows: Matheuristics and new instances. Computers & Operations Research, 124, 105065.

New instances

Another part of my MSc. project was to generate new, more realistic instances with different characteristics to those of the standard benchmark set introduced by Li & Lim (2003). We used open data to create instances with real-world locations and travel times. The results that we obtained using our new benchmark set diverged somewhat from those obtained with the standard benchmark, which seems to indicate that these sets do have intrinsic differences.

Contributions from this part of the project:

  1. Instances, results and a solution validator.
  2. An open source instance generator.

In addition to the previous contributions, we have written a short tutorial for the brazilian Operations Research journal Pesquisa Operacional para o Desenvolvimento (PODes) about generating vehicle routing instances using open data. The tutorial is available (in portuguese):

  1. Sartori, C. S., & Buriol, L. S. (2020). Instâncias para roteamento de veículos usando dados abertos. Pesquisa Operacional para o Desenvolvimento, 12, 1-11.

Iterated variable neighborhood descent

During my BSc. in Computer Science, my final thesis (TCC, in Brazil) also revolved around solving the PDPTW. I developed a pure metaheuristic using a combination of Iterated Local Search and Variable Neighborhood Descent. Among the neighborhoods implemented: shift request, exchange request and rearrange request. All of them classical local search moves for the PDPTW. Results were not necessarily competitive with the state of the art. However, the project allowed me to gain a lot of research experience and knowledge about vehicle routing which later helped my MSc. research (above).

The results of my BSc. thesis were also published in the Brazilian Symposium on Operations Research (SBPO, 2017) within the undergraduate research projects track.

  • Sartori, C. S., Friske, M. W., & Buriol, L. S. (2017). An Iterated Variable Neighborhood Descent Algorithm applied to the Pickup and Delivery Problem with Time Windows. XLIX - Simpósio Brasileiro de Pesquisa Operacional.

Achievements

This project led to two achievements.

  1. Nomination for best BSc. project award in Brazil at XLIX - Simpósio Brasileiro de Pesquisa Operacional 2017 (5 projects were nomindated).
  2. Best MSc. thesis award at LII - Simpósio Brasileiro de Pesquisa Operacional 2020.

References

  1. [Furtado et al., 2017] – Furtado, M. G. S., Munari, P., & Morabito, R. (2017). Pickup and delivery problem with time windows: a new compact two-index formulation. Operations Research Letters, 45(4), 334-341.
  2. [Blum et al., 2016] – Blum, C., Pinacho, P., López-Ibáñez, M., & Lozano, J. A. (2016). Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Computers & Operations Research, 68, 75-88.
  3. [Curtois et al, 2018] – Curtois, T., Landa-Silva, D., Qu, Y., & Laesanklang, W. (2018). Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows. EURO Journal on Transportation and Logistics, 7(2), 151-192.
  4. [Lourenço et al., 2003] – Lourenço, H. R., Martin, O. C., & Stützle, T. (2003). Iterated local search. In Handbook of metaheuristics (pp. 320-353). Springer, Boston, MA.
  5. [Li & Lim, 2003] – Li, H., & Lim, A. (2003). A metaheuristic for the pickup and delivery problem with time windows. International Journal on Artificial Intelligence Tools, 12(02), 173-186.