1. Company introduction

It is a comprehensive energy service corporation that supplies city gas throughout Daejeon Metropolitan City and Gyeryong City since its establishment in 1985.

※ In October 2017, the name was changed from Chungnam Urban Gas Co., Ltd. to CNCITY Energy Co., Ltd.

2. Problem Background and Summary

To ensure the safe management of city gas, a person in charge of each district conducts a daily inspection of gas pipeline burial areas and solves events (checking excavation work, handling civil complaints, etc.). Because the time and location of the event are different each time, the location of the remaining pipes to be checked after the event is always different, and the current inspection order of the remaining pipes is determined solely from the experience of the person in charge.

Using mathematical principles such as graph theory, etc., the goal is to develop an algorithm to find the optimal route for the remaining piping circuit inspection, to check if the current method is the best, and to find a more efficient way of circuit inspection.

3. Solving Process

An algorithm was developed to print the shortest route back to the head office when the current location and remaining pipes were entered.

Utilizing the principles of Chinese Postman Problem and Minimal perfect matching in graph theory, we find the shortest path, and show this on the map.

4. Ripple effects and future plans

Identifying the possibility of optimal circuit inspection routing using the developed algorithm