Tactical crew planning at Turkish state railways

Abstract

Türkiye Cumhuriyeti Devlet Demiryolları'nda (TCDD) taktik seviyede ekip planlama problemi, ekip bölgelerinin önceden genel merkez tarafından belirlenmiş çizelgelerindeki görevleri gerçekleştirecek enküçük ekip üyesi sayısının belirlenmesini kapsar. Problem, şirketin gereksinimleriyle ilgili kural ve kısıtları sağlayarak her bölge için ayrı ayrı çözülür. Bu kısıtlardan en önemlilerinden biri de problemin çözümünü zorlaştıran tatil günü kısıtıdır. Bu çalışmada, taktik seviyede kapasite planlama problemini tatil günü kısıtıyla çözmek için bir uzay-zaman çizgesi gösterimi kullanıyoruz. Problemi çözmek için iki çözüm yaklaşımı geliştiriyoruz: ardışık yaklaşım ve tümleşik yaklaşım. Ardışık yaklaşımda halihazırda TCDD'de kullanılan çözüm yaklaşımını taklit ederek problemi iki aşamada çözeriz. İlk aşamada bir uzay-zaman çizgesi üzerinde tatil günü kısıtını göz ardı ederek bir enküçük akış problemi çözeriz. İkinci aşamada ise, bu problemin çözümünden elde edilen kesin olmayan ekip çizelgeleri üzerine yedek ekip üyeleri kullanarak tatil günlerini doldurmak için bir atama problemi çözeriz. Tümleşik yaklaşımda ise katmanlı bir uzay-zaman çizgesinde yan kısıtları olan enküçük akış problemi çözeriz. Bilgisayısal çalışmamızı TCDD'den alınan gerçek veri kümeleri üzerinde sunuyoruz. Taktik seviyede ekip planlama probleminden sonra daha üst seviyede bir ekip kapasite planlama problemini ele alıyoruz. Bu taktik-stratejik arası seviyedeki kapasite planlama probleminde birden çok bölgeyi aynı anda düşünerek bölgelerde ihtiyaç duyulan toplam ekip üyesi sayısını enküçükleriz. Bunu gerçekleştirmek için, görevlerin farklı bölgelere atanmasını ve bölgeler arası görev paylaşımı seçeneklerini değerlendiririz. Tek bölgeli ve iki bölgeli taktik-stratejik arası seviyedeki kapasite planlama problemlerinin farklı görev paylaşım kurallarıyla matematiksel modellerini sunuyoruz. Problemin büyük ölçekli olması sebebiyle açgözlü bir yöre araması algoritmasıyla problemi çözeriz. Açgözlü yöre araması algoritmasında ardışık çözümde geliştirdiğimiz enküçük akış problemini altyordam olarak kullanırız. Bilgisayısal çalışmayı yine TCDD veri kümesi üzerinde sunuyoruz.

Tactical crew planning problem at Turkish State Railways (TCDD) involves finding the minimum crew capacity in a crew region required to operate a predetermined set of train duties assigned to the region by the headquarters. The problem is to be solved for each crew region by satisfying various rules and constraints associated with the requirements of the company. One of the most important constraints is the day-off requirement which makes the problem computationally intractable. In this study, we use a space-time network flow representation to solve the tactical capacity planning problem with day-off requirement. To solve the problem, we develop two solution approaches: the sequential approach and the integrated approach. In the sequential approach we mimic the current practice at TCDD and solve the problem in two stages. In the first stage, we solve a minimum flow problem over a space-time network by relaxing the day-off requirement. After obtaining the tentative schedules of crew members, we solve an assignment problem to fill-in the days-off in the tentative schedules by using additional substitute crew members. In the integrated approach, we solve a minimum flow problem with side constraints using a layered space-time network representation of the problem. We present the computational study on a real-life data set acquired from TCDD. We, then, study a higher level crew capacity planning problem. In this tactical-to-strategic level capacity planning problem, we minimize the total crew capacity of all regions by simultaneously considering multiple regions. We do this by re-assigning duties to different regions or allowing two neighboring crew regions share the train duties in different settings. For tactical-to-strategic capacity planning problem, we present the mathematical formulation of single-region and two-region models with various crew exchange policies. Given the large scale of the search space, we choose to employ a neighborhood search heuristic in order to solve the problem. The neighborhood search heuristic uses the minimum flow problem in the sequential approach as a subprocedure. We present the computational study again for the TCDD data set.