Districting with LIZARD

Project description


From July 2010 to June 2014 the chair for Discrete Optimization and Logistics (DOL) at KIT developed an open source application that enables the user to solve districting problems with LIZARD (LIbrary of optimiZation AlgoRithms for Districting).

The algorithms of LIZARD are triggered via a geographic information system (GIS). The web GIS was implemented using OpenLayers API and OpenStreetMap GIS. The user interface is shown in the web browser so can be called without any local installation of software. Zooming in or out, moving the map and placing locations are operations the user can handle without being faced with the mathematical details of algorithms.

Besides a high uptime and usability of LIZARD, visualization of results is a great win of the web GIS. After placing basic areas in the web browser by clicking on the map the calculated result is shown in the web browser as well.

An important application of the web GIS is teaching. The lecture "Location planning and strategic supply chain management" gives the theoretical background to understand the algorithms used by LIZARD. For visualization and a better understanding of the contents examples can be calculated with the web GIS in order to analyze the results.


  • The "Recursive Partitioning Algorithm" has been presented in:
    J. Kalcsics, S. Nickel und M. Schröder: Towards a Unified Territorial Design Approach - Applications, Algorithms and GIS Integration, TOP 13(1), 1-74 (2005).
  • Several practical extensions of the "Recursive Partitioning Algorithm" and the Power Diagram Districting Algorithm are described in:  A.Butsch: Districting Problems - New Geometrically Motivated Approaches, PHD-Thesis 2016, http://dx.doi.org/10.5445/IR/1000058069
  • The heuristic solution approach to solve districting problems based on streets was published in:
    A.Butsch, J. Kalcsics, G. Laporte: Districting for arc routing, INFORMS Journal on Computing 26(4), 809-824, 2014.