고객 정보 공유를 고려한 지속가능 렌탈 서비스 기업의 방문 서비스원 경로 계획

1. 서 론

고객에게 필요한 물건을 대여해주고 대여 물품의 무상 교체 등의 서비스를 제공하는 렌탈 시장은 꾸준히 성장 중이다. 2006년 3조 원이었던 국내 렌탈 시장 규모는 2020년에 40조 원을 넘어섰으며, 오는 2025년에는 100조 원에 달할 전망이다(Kim, 2023). 렌탈 서비스 기업은 방문 서비스원을 통해 고객의 요구시간에 맞추어 설치와 필터 교체 등의 서비스를 제공한다. 그러므로 방문 서비스원이 고객에게 제공하는 서비스가 고객의 만족도를 결정하고, 고객 만족도는 기업의 운영비용에 영향을 미친다. 렌탈 서비스 시장이 커지고 있는 상황에서 지속 가능한 기업을 위해 방문 서비스원의 중요성이 강조되고 있으나(Jung, 2021), 최근 방문 서비스원의 기업 이탈이 계속해서 발생하고 있다(Kim, 2022). 이에 따라 고객 서비스 만족도 하락과 기업의 운영비용이 증가하여 기업 지속 가능성을 위협하고 있다.

방문 서비스원은 특수고용 노동자로 다음과 같은 두 가지 문제를 가지며, 이는 방문 서비스원의 기업 이탈을 야기한다. 첫 번째로 방문 서비스원은 시간 대비 최저임금이 보장되지 않는다. 방문 서비스원은 제공한 점검 서비스에 대한 건당 수수료를 렌탈 기업으로부터 지급 받고, 담당하는 고객에게 방문하는 시간과 방문 순서를 결정한다. 현실에서는 처리해야 할 고객이 많기 때문에 서비스원의 의사결정이 복잡하다. 이로 인해 서비스원의 이동시간이 길어져 근무 시간 대비 수익 미보장을 야기한다. 두 번째로 방문 서비스원은 근무 자유도가 낮다. 방문 서비스원의 경우, 근무시간이 정해진 것이 아닌 고객의 요구시간에 따라 근무시작시간과 종료시간이 결정되는 비확정적인 근무시간을 가진다. 이는 방문 서비스원의 근무 자유도를 하락시킨다. 이에 본 연구에서는 지속적인 기업 경영을 위해 서비스원의 시간 대비 최저 임금 보장과 근무 자유도 및 고객 만족도를 반영한 새로운 통합 운영 전략을 제시하고자 한다.

제시한 운영 전략에서는 네 가지 세부 사항을 고려한다. 첫 번째로 방문 서비스원들이 담당하고 있던 고객의 일부를 공유한다. 서비스원이 담당하고 있는 고객은 회사가 소유한 고객과 서비스원이 영업을 통해 얻은 고객으로 분류할 수 있다. 영업을 통해 얻은 고객은 서비스원의 영업적 수익을 보장하기 위해 공유하지 않는다. 대신 회사가 소유하고 있는 고객의 공유를 통해 효율적인 동선의 라우팅을 목표로 한다. 두 번째로 서비스원의 희망근무시간을 고려한다. 방문 서비스원의 이탈 요소 중 하나인 비확정적인 근무시간을 해결하기 위해, 희망근무시간을 설정한다. 희망근무시간 외 작업들은 다른 서비스원에게 할당하거나, 추가근무로 처리한다. 세 번째로 시간어김비용을 고려한다. 고객의 방문 요구시간을 벗어나는 서비스는 고객의 불만족을 발생시킨다. 따라서 방문 요구시간을 벗어나는 서비스에 대해 잠재적 고객 불만족비용인 시간어김비용을 반영했다. 네 번째는 효율적인 경로계획으로 줄어든 기업운영비를 시간 대비 최저임금이 미충족 된 서비스원의 지원을 위해 사용한다. 이러한 운영전략 제시를 통해, 방문 서비스원과 고객의 일정을 모두 고려한 통합적 경로계획을 연구하고자 한다.

연구하고자 하는 렌탈 서비스 기업의 방문 서비스원 경로계획을 위해 기업의 운영비용을 고려한 이동 거리에 따른 비용, 방문 서비스원의 소득 보장 및 자유도를 고려한 미충족급여와 추가 근무수당, 그리고 고객 만족도를 고려한 시간어김비용을 최소화하는 목적함수를 수립했다. 주요 의사결정사항으로는 방문 서비스원이 서비스를 제공할 고객 할당, 방문순서 그리고 방문시간이 있다. 주요 제약으로는 공유 비율 제한, 방문 서비스원이 영업한 고객의 공유 제한 제약 등이 있다.

본 연구에서는 지속가능한 기업 경영을 위해 제시한 전략을 포함한 경로계획을 수행하기 위해서 혼합정수선형계획법(Mixed Integer Linear Programming: MILP)을 수립하고, 메타휴리스틱을 활용하였다. 본 논문의 구성은 다음과 같다. 2장에서는 선행 연구와의 비교를 진행한다. 3장에서는 방문 서비스원의 수익 구조로부터 나오는 렌탈 서비스 기업의 문제를 정의하고 정의한 문제를 MILP 수리모형으로 나타냈다. 4장에서는 메타휴리스틱 기법인 유전 알고리즘(Genetic Algorithms)과 입자 군집 최적화(Particle Swarm Optimization)를 제안한다. 5장에서는 제안된 휴리스틱 방법론과 기존 근무방식을 임의로 모방한 세 가지 룰과 비교하고 도입효과를 분석한다. 또한, 고객 정보를 공유하는 것에 대한 효과를 검증한다. 마지막으로 제6장에서는 결론을 제시한다.

2. 선행연구

본 논문은 근무시간이 존재하는 근무자가 고객의 요구시간대에 방문하여 서비스를 제공하는 방문 서비스원의 경로계획을 연구한다. 따라서 시간 제약이 있는 차량경로설정문제(Vehicle Routing Problem with Time Window: VRPTW)와 관련된 최근 선행연구들을 조사하였다.

다음의 연구들은 특별한 제약상황에서 방문하는 차량에 대해 경로를 설정하는 선행연구이다. Errico et al.(2018)에서는 강한 시간 제약과 서비스시간이 확률변수로 나타나는 문제를 연구하였고, Li et al.(2010)에서는 이동시간과 서비스시간이 확률적인 문제를 제시하고 타부서치 기반 휴리스틱 방법론을 사용하였다. Pureza et al.(2012)에서는 긴 서비스시간으로 근무시간 내 모든 수요를 처리하기 어려운 상황에서, 경로에 배송원을 추가하는 방법으로 서비스시간과 비용을 최소화하는 모델을 제시하였다. Arias-Melia et al.(2022)에서는 방문서비스를 진행하며 서비스시간동안 경로상의 차량을 공유하는 문제를 수리모형과 휴리스틱 방법론으로 연구하였다. Korcyl et al.(2019)에서는 방문시간과 수거시간이 존재하고, 종류가 다른 차량을 라우팅하는 수리모델을 수립하였다.

다음의 연구들은 Burke et al.(2004)에서 제안된 근무일정문제와 결합되어 VRPTW에서 확장된 선행 연구들이다. Liu and Xie(2013)에서는 방문 간호서비스를 제공하기 위해 고객과 간호사의 요구시간을 고려하는 제약하에서 유류비를 최소화하는 목적함수로 연구를 진행하였다. 초과근무를 고려하며 제약 어김을 최소화하거나(Hiermann et al., 2015), 고객의 선호도 및 휴일과 쉬는시간 등 근무자의 휴게시간을 고려하는 연구가 제시되었다(Wirnitzer et al., 2016). Nickel et al.(2012)에서는 방문 간호사의 초과 임금을 최소화하는 목적함수를 사용하여 스케줄링하였다. Bazirha et al.(2023)에서는 방문 간호를 위해 다중시간대를 고려한 2단계 휴리스틱을 제안하였다. Tsang and Shehadeh(2023)에서는 방문 서비스 근무자 한 명에 대해 무작위로 발생하는 수요를 처리하기 위한 확률적 최적화 모델을 제시하였다. 목적함수로 운영비용을 최소화하기 위해 고객의 대기시간과 근무자의 이동시간, 유휴 및 초과근무시간을 고려하였다.

<Table 1>에서 보듯이 최근 15년간 선행 연구에서 방문 서비스원의 효율적인 운영을 위한 연구가 이뤄지고 있다. 해결하려는 렌탈서비스 기업의 특징은 특수고용노동자인 근무자들을 소유하고 있고, 그 근무자들의 수익 보장이 되지 않는 문제와 고객의 요청시간으로 인한 근무 자유도가 낮은 특징을 가지고 있다(Choi, 2022). 또한, 고객의 위치, 담당하는 근무자의 여부, 방문 요구시간 등 고객 정보에 따라 근무자가 직접 의사결정하는 것이 특징인데, 이 고객 정보의 공유를 고려한 문제에 대한 연구는 진행되지 않았다.

Table 1.

Classification of VRPTW Problem Studies

따라서 본 연구의 학문적 기여는 다음과 같다. 첫 번째로, 방문 서비스원의 이탈을 방지하기 위하여 수익을 보장하는 것을 고려했다. 선행 연구들은 목적함수로 차량의 이동 비용 등 기업의 운영 관점에서의 비용을 다뤘지만, 본 연구는 기업의 지속 가능성을 위해 서비스원의 시간 대비 수익 보장을 고려했다. 효율적인 일정 및 동선으로 인하여 줄어든 비용을 방문 서비스원의 시간대비 최저수익에 미충족된 급여를 보장하는 비용으로 고려했다. 두 번째로, 렌탈 서비스 기업의 지속가능 관점에서 기업과 서비스원, 그리고 고객을 모두 고려하는 운영 전략을 제시하고, 이를 최적화 기법으로 풀어냈다. 방문 서비스원의 계약 형태로부터 발생하는 문제 해결을 위하여 MILP, 유전 알고리즘 및 입자 군집 최적화 방법론을 사용해 기업의 운영비용을 절감하는 서비스원들의 효율적인 경로를 제시하였다.

3. 문제 설명 및 수리모형

일반적인 VRPTW 문제는 다음과 같은 가정 및 제약이 있다. 첫 번째로, 모든 고객은 서비스를 제공 받아야 한다. 두 번째로, 근무자는 출발지에서 출발하여 출발지로 돌아온다. 세 번째로, 근무자가 고객의 위치로 이동하여 방문하는 것과 서비스를 제공하는데 소요하는 시간을 고려해야 한다. 네 번째로, 근무자 수와 고객 수는 고정되어 있으며 고객의 요구시간이 존재한다. 본 연구에서 제시하는 문제는 기존 VRPTW에서 확대된 형태로 시간제약이 있는 서비스원의 경로계획문제(Service-worker Routing Problem with Time Window: SRPTW)로 정의된다. 기존의 VRP 연구들은 목적함수로 차량의 이동비용 등 기업의 운영 관점의 비용을 고려했다면, 본 연구는 렌탈 서비스 기업의 특징으로 인해 발생하는 문제를 다루고, 이를 해결하기 위해 서론에서 제시한 운영 전략을 반영한다.

지속가능한 관점에서 기업을 운영하기 위해 운영비용, 고객의 만족도 그리고 근무자의 이탈을 방지하는 것이 매우 중요하다. 따라서 서비스원의 자유도와 수익을 보장하며 고객의 만족도를 고려하는 목적함수를 수립했다. 목적함수는 결정된 순서와 시간에 따라 발생하는 유류비, 시간어김비용, 추가근무수당 그리고 미충족수당의 총합을 최소화하는 문제이다. 고객의 요청시간을 준수하지 못한 비용은 시간어김비용, 서비스원의 근무요청시간 초과에 대한 비용은 추가근무수당이라 한다. 서비스원의 소득과 실제 근무한 시간을 최저시급에 적용하여 비교했을 때 부족한 급여는 미충족수당이라고 한다. 제시한 운영 전략을 반영하기 위하여 다음과 같은 가정 및 제약사항들이 존재한다. 첫째로, 개인의 소득 보장을 위해 영업을 통한 고객은 영업한 방문 서비스원이 반드시 처리하도록 하고 회사 소유 고객의 60%는 어떤 방문 서비스원이든 할당될 수 있도록 한다. 두 번째로, 고객은 방문요청시간과 기존 담당서비스원의 정보가 있으며, 고객을 방문하는 날짜는 주어진다고 가정하여 의사결정하지 않는다. 방문 요청 시간을 벗어나는 서비스는 고객의 만족도 하락을 고려하여 패널티 비용을 산정한다. 마지막으로, 방문 서비스원은 희망근무시간을 요구하되, 기존에 담당하고 있는 영업고객의 수에 비례한 최소 근무시간 이상으로 희망 근무시간을 신청할 수 있다. 희망 근무시간 내에 존재하지 않는 고객은 다른 근무자에게 할당되거나, 기존 근무자에게 추가 근무수당을 지불하여 할당되도록 한다.

<Table 2>와 <Figure 1>은 문제설명의 이해를 돕기 위해 작은 인스턴스를 통해 고객 10명 서비스원 2명일 때의 상황에서의 라우팅 예시를 보인다. <Table 2>는 고객과 서비스원의 파라미터로 고객의 수, 방문 요청 날짜와 시간, 담당하는 서비스원, 고객공유가능 여부 그리고 서비스원의 희망근무시간을 나타낸다. 서비스 소요시간은 고객마다 다를 수 있으나 <Table 2>의 문제상황에서는 30분으로 통일한다.

Table 2.

Client and Worker Information

Figure 1.

An Illustrative Example of Routing and Gantt Chart

<Figure 1>에서는 <Table 2>를 기반으로 라우팅된 상황을 예시로 다루고 있으며, 서비스원에게 할당된 고객과 방문시간을 보여준다. 본 문제에서는 먼저 고객마다 방문할 서비스원을 할당한다. 할당 과정에서는 공유 불가능 고객과 가능 고객을 고려하고 고객의 서비스요청날짜에 따라 할당한다. 이후 방문할 고객들의 순서와 시간을 결정한다. 이 과정에서 순서와 시간은 고객의 요청시간과 서비스원의 희망근무시간에 따라 결정되며 목적함수에 해당하는 비용 요소들의 비교를 통하여 비용이 최소가 되는 시간과 순서로 결정된다.

Day 1에서는 Worker 1에게 C3, C4, C5가 할당되었고, C1, C2가 Worker 2에게 할당되었다. C1, C2는 서비스원이 영업을 통해 얻은, 공유가 불가능한 고객이기 때문에 본래 담당하는 Worker 2에게 할당되었으며, C3는 공유가 가능한 고객으로 라우팅 과정에서 목적함수 비교를 통해 Worker 1에게 공유되어 할당되었음을 나타낸다. C4와 C5는 회사가 소유한 고객, 즉 공유가 가능한 고객이지만 목적함수 비교를 통해 기존대로 할당된 상황을 나타낸다. <Figure 1>의 아래 간트 차트는 최종 할당된 고객의 순서와 처리 시간을 포함하는 간트차트이다. 회색으로 표시된 서비스원의 희망근무시간이 나타나 있으며, 그 안에 고객 처리시간이 나타나 있다. Day 1의 Worker 1은 요구한 희망근무시간 내에 C4, C3, C5 순서대로 서비스를 처리하는 모습이고, Worker 2는 C1, C2 순서로 서비스를 진행하고 C1이 서비스원의 희망근무시간보다 앞서 처리되는데 이 경우 시간 외 비용인 추가근무수당이 지급된다. C1, C2 시간 결정 이유는 대기가 없는 문제 상황에서 고객에서 고객으로 바로 이동해야 하는데, 고객의 요청시간을 지각하는 경우의 비용이 요청시간 보다 일찍 서비스 하는 비용보다 두 배로 설정되어 있다(Lin Li, 2020). 이러한 비용을 고려하여 고객 C1을 요청시간 내에 처리하고 고객 C2를 일찍 서비스하게 되었다. Day 2 에서는, Worker 1에게 C6, C7, C9, C10이 할당되었고, Worker 2에게는 C8만 할당되었다. C7과 C8은 공유가 불가능한 고객이기에 각각 담당하는 서비스원에게 할당되었고, C6, C9, C10은 공유가 가능한 고객이며, 그 중 C6은 목적함수 비교에 따라 Worker 2의 고객이 Worker 1에게 공유되어 할당되었다. Day 2의 Woker 1의 경우 요구한 희망근무시간 내에 C7, C9, C6, C10 순서대로 서비스를 처리하는 모습이고, Worker 2도 요구한 희망근무시간 내에 C8 서비스를 처리하는 모습이다.

아래는 SRPTW를 해결하기 위한 MILP 모형이다.

Sets and Parameters

Decision Variables

목적함수와 제약식은 다음과 같다.

Subject to

목적함수는 유류비, 서비스원의 추가근무수당, 미중촉수당 그리고 시간어김비용을 최소화하는 것이다. 제약식 (2)는 현재 위치에서 제자리 이동을 방지한다. 제약식 (3)과 (4)는 지국에서 반드시 출발하고 도착해야 한다는 제약이다. 지국은 한 개만 고려한다(|D|=1　). 제약식 (5)는 고객의 방문 가능 날짜에만 서비스원이 방문할 수 있도록 하는 제약이다. 제약식 (6)은 서비스원이 특정 고객을 방문했을 경우 지국을 포함한 다른 고객들 중에서 특정 고객으로 무조건 한 번 이동해왔어야 한다는 제약이다. 제약식 (7)은 서비스원이 특정 고객을 방문했을 경우 지국을 포함한 다른 고객들로 특정 고객이 무조건 한 번 이동해야 한다는 제약이다. 제약식 (8)과 (9)는 서비스원이 지국을 포함하여 모든 고객에 대해 하루 두 번 이상 방문하지 못한다는 제약이다. 제약식 (10)은 모든 수요를 만족시켜야 한다는 제약이다. 제약식 (11)은 방문하지 않는 고객의 방문시간을 0으로 제한한다. 제약식 (12)와 (13))은 고객의 서비스 요청시간 하한과 상한을 벗어난 시간을 측정하는 제약이다. 제약식 (14)와 (15)는 현재 고객과 다음에 방문할 고객 사이의 시간 관계식이다.제약식 (16)은 방문 서비스원의 근무시작을 결정하는 제약으로 지국에서 출발하는 시간이다. 제약식 (17)은 방문 서비스원의 근무종료시간을 결정하는 제약으로 최종적으로 지국에 도착하는 시간이다. 제약식 (18)과 (19)는 서비스원의 근무요청시간을 벗어난 추가근무를 측정하는 제약이다. 제약식 (20)은 고객 0(지국)의 순서를 제약해 항상 가장 먼저 방문하게 한다. 제약식 (21)은 현재 고객과 다음에 방문할 고객 사이의 순서 관계식이다. 제약식 (22)는 고객들이 가질 수 있는 최대순서를 제한하여 서브투어에 빠지는 것을 방지하기 위한 제약이다. 제약식 (23)은 담당서비스원의 변경여부를 확인하는 제약이다. 제약식 (24)는 회사가 소유한 고객만 공유가 가능하다는 제약이다. 제약식 (25)는 회사가 소유한 고객의 공유가능한 비율에 따라 공유가능 횟수를 제한하는 제약이다. 제약식 (26)은 서비스원별로 이동에 따른 유류비를 계산하는 제약이다. 제약식 (27)은 서비스원별로 추가근무수당을 계산하는 제약이다. 제약식 (28)은 서비스원별로 미충족수당을 계산하는 제약이다. 제약식 (29)는 고객별로 요청시간어김비용을 계산하는 제약이다.

4. 메타휴리스틱

VRP는 NP-hard한 문제로 알려져 있다(Mohammad et al., 2022). SRPTW는 VRP에 시간 제약이 추가된 형태로 고객과 서비스원 간의 관계를 고려해야 하므로 기본적인 VRP보다 더 복잡한 문제이다. 이로 인해 제3장에서 제안한 MILP만으로는 현실적 크기의 문제에 대해 제한된 시간 내에 최적해를 찾기 어려운 상황이 발생한다. 따라서 본 논문에서는 최적해를 보장하지는 못하지만, 근사해를 빠르게 찾아주는 메타휴리스틱을 개발할 필요성이 있다. 제4장에는 VRP의 효과적인 해의 성능을 보여주는 유전 알고리즘(Genetic Algorithm: GA)과 입자 군집 최적화(Particle Swarm Optimization: PSO) 두 가지 메타휴리스틱을 개발한다. 두 알고리즘은 동일한 해 구조를 가지고 있으며, Iswari et al.(2018)처럼 두 알고리즘은 VRP 문제를 효과적으로 풀기 위해 사용되었다.

4.1 해의 표현과 디코딩 과정

본 연구에서는 SRPTW를 위한 GA와 PSO의 염색체 및 입자를 <Figure 2> (a)와 같이 제안한다. <Figure 2>는 문제정의에서 사용한 데이터로 고객 10명, 서비스원 2명, 날짜 2일의 상황이고 각 열은 고객을 의미한다. <Figure 2> (a)는 독립적인 1차원 행렬 2개로 이루어져 있으며 1행은 해당 고객에 방문할 서비스원을 나타내고 [1, |I|] 사이의 무작위 정수로 표현되며 해의 길이는 고객수와 같다. 2행은 고객의 처리 순서를 나타내고 0부터 1사이의 무작위 실수로 표현되며 해의 길이는 고객수와 같다.

Figure 2.

Example of Decoding Process

아래 <Figure 2>는 <Figure 2> (a)의 인코딩된 해를 디코딩하는 과정을 그림으로 나타낸 것이다. 먼저 인코딩된 해 a를 방문할 서비스원이 같은 고객끼리 분류해 서비스원 1과 2가 처리해야 할 고객집합으로 분류한다. b의 1행은 방문할 서비스원을 나타내고 2행은 1행의 서비스원이 방문할 고객을 의미한다. c는 서비스원에 따라 분류된 b를 고객의 방문요청일에 따라 추가로 분류한 표이다. 1행은 b와 마찬가지로 방문할 서비스원을 나타내고 2행은 방문요청일을 나타내며, 3행은 1행과 2행에 따라 분류된 고객들이다. 서비스원과 날짜에 따라 분류된 c를 본 문제의 제약 중 하나인 ‘영업고객은 담당서비스원이 무조건 방문해야한다’는 제약에 따라 <Table 2>의 영업고객 여부와 담당서비스원을 비교해 영업고객이면서도 담당서비스원이 다른 고객들의 서비스원 할당을 취소하고 다시 원래의 담당서비스원으로 할당해야한다. 따라서 c의 서비스원 1의 C1과 C8을 서비스원 2로 서비스원 2의 C7을 서비스원 1로 재할당하여 d가 된다. 마찬가지로 회사소유의 고객인 경우에도 제약이 존재한다. 이는 설문조사에 의한 결과로, 고객의 서비스만족도를 보장하기 위한 제약이다. 현재 회사소유의 고객 6개 중 60%인 3.6개 미만으로만 공유 가능하다는 제약으로 최대 3개까지만 기존 담당서비스원이 아닌 서비스원에게 할당 가능하다. 현재 4개의 고객이 공유되었기 때문에 제약을 지켜주기 위해 몇몇의 공유된 고객을 다시 기존 담당서비스원에게 재할당시켜야 하며 무작위로 시행한 결과 C4가 서비스원 2에서 서비스원 1로 재할당되어 e의 모습이 되었다. 마지막으로 a의 분포에 따라 무작위로 생성된 고객의 랜덤키를 이용해 오름차순에 따라 정렬하면 방문순서가 결정되어 f의 모습이 되고 디코딩 과정은 끝난다. 가장 하위에 있는 집합은 일반적으로 TSP문제에서 사용하는 ‘경로표현법’의 형태를 띄게 되고 예시로 <Figure 2> (f)에서 서비스원 1은 Day1에 지국에서 출발해 고객 4를 처음 방문하고 고객 3을 두 번째로 방문한 뒤, 마지막으로 고객 5를 방문한 후 지국으로 돌아옴을 의미한다.

할당과 순서가 결정된 이후 고객에게 방문할 시간과 서비스원들의 근무시간을 결정해야 한다. 고객의 방문요청시간 이전에 방문하는 경우 서비스원이 대기하지 않고 시간어김비용으로 처리하기 때문에 서비스원의 근무시작시간을 결정하면 방문할 고객과 순서가 존재하는 상황에서 고객에 방문할 시간들이 모두 연속적으로 결정된다. 시작시간이 변경됨에 따라 목적함수의 구성요소 중 고객시간어김비용, 추가근무수당, 미충족수당이 바뀔 수 있으므로, 본 연구에서는 9시부터 18시까지 10분 단위로 근무시작시간을 증가시키며 비용의 합이 가장 작은 지점을 해당 서비스원의 시작시간으로 결정하기로 한다.

4.2 유전알고리즘과 입자군집최적화

GA와 PSO는 대표적인 집단 기반 메타휴리스틱이다. 다양한 조합 최적화 문제에서 뛰어난 성능을 보여주었기 때문에 본 논문에서도 이 두 알고리즘을 사용해 SRPTW를 풀었다. 본 연구에서 GA의 구조는 초기화 단계, 적합도 평가단계, 선택단계, 교차단계, 돌연변이 단계, 및 대체단계로 구성된다. 초기화 단계에서는 각행의 분포에 따라서 무작위로 생성한다. 본 논문의 적합도 함수는 3장에서 제시한 MILP의 목적함수를 사용해 나타냈다. 목적함수 Z는 유류비, 서비스원의 추가근무수당, 미중촉급여 그리고 시간어김비용의 합이다.

$\[ Fittness =\frac{1}{ MinimizeZ }. \]$

(30)

이후 <Figure 3>에서와 같이 선택(Selection), 교차(Crossover), 돌연변이(Mutation)와 같은 절차를 따라 세대를 진행한다. 선택 단계에서는 룰렛 휠 방법(Roulette wheel selection)을 사용하였다. 교차단계에서는 방문할 서비스원 염색체와 랜덤키 염색체 모두 1점 교차방법(Single point crossover)을 사용하였다. 균등분포 돌연변이는 무작위로 선택된 염색체 및 입자의 유전자 분포에 맞게 재표현 된다. 현재 바뀐 모집단은 다시 선택 과정을 거쳐 다음 세대의 모집단이 된다. 이러한 GA 과정은 미리 설정한 종료조건이 될 때까지 반복된다.

Figure 3.

GA Pseudo-code

PSO의 경우, GA와 같은 초기해 생성방식, 적합도 평가방식을 따른다. 본 논문에서 사용하고 있는 해는 이산적인 형태로 실수해 공간에서 작동하는 PSO를 나타내기에는 부족하다. 따라서 일반적인 PSO가 아닌 이산적인 PSO(Discrete Particle Swarm Optimization: DPSO)를 통해 문제를 해결하고자 한다. DPSO는 Pan et al.(2008)에 의해 제안된 알고리즘으로, 이산형 최적화문제에서 사용할 수 있도록 하기 위해 새로운 위치 업데이트 방법을 도입한 PSO이다. 이 방법에서는 입자의 위치가 한 번에 업데이트되어 속도를 고려하지 않는다.

$\[ x_i^t=c_2\otimes F_3\left(c_1\otimes F_2\left(w\otimes F_1\left(x_i^{t-1}\right),p_i^{t-1}\right),g_i^{t-1}\right). \]$

(31)

$$ x_i^t$$는 시점 t에 입자 i의 위치이다. $$ p_i^{t-1}$$, $$ g_i^{t-1}$$는 각각 t - 1시점에 입자 i의 개인최적해와 집단최적해이다. 식 (31)은 $$ x_i^t$$를 업데이트하는 식이다. 관성가중치 w, 개인 최적해 및 집단 최적해를 고려하는 상수 c₁,c₂는 0부터 1사이 실수값을 가진다. F₁은 확률 w에 의한 돌연변이 연산자로, 0부터 1사이 값으로 생성된 수가 w보다 작으면 돌연변이가 발생한다. $$ x_i^{t-1}$$가 돌연변이가 발생하여 생긴 새로운 입자를 $$ {\lambda }_i^t$$라고 하자. F₂는 인지요소로 개인최적해 교차확률 c₁에 의해 $$ p_i^{t-1}$$와 교차를 발생시킨다. 이전 t - 1시점에서 돌연변이로 생긴 입자 $$ {\lambda }_i^{t-1}$$를 $$ p_i^{t-1}$$와 교차하여 생긴 새로운 입자를 $$ {\delta }_i^t$$라고 하자. F₃은 사회요소로 집단최적해 교차확률 c₂에 의해 $$ g_i^{t-1}$$와 교차를 발생시킨다. 이전 t - 1시점에서 교차로 생긴 $$ {\delta }_i^{t-1}$$를 $$ g_i^{t-1}$$와 교차하여 생긴 입자가 $$ x_i^t$$가 된다. 본 연구에서는 1점 교차를 통해 확률적으로 위치가 이동한다고 가정하며 확률적으로 입자에서 돌연변이가 발생해 방문할 서비스원과 방문순서를 변경한다. 이러한 DPSO는 GA와 마찬가지로 미리 설정한 종료조건이 될 때까지 반복된다. <Figure 4>는 위의 내용을 정리한 DPSO의 수도코드이다.

Figure 4.

DPSO Pseudo-code

5. 실 험

본 장에서는 3장에서 개발한 MILP를 CPLEX solver를 활용해 최적해를 도출하고, 메타휴리스틱 알고리즘의 최적해 탐색 능력을 검증하기 위해 비교한다. 또한, 두 메타휴리스틱 알고리즘의 성능을 비교하기 위해 현실적인 크기의 문제에서 실험하였고, 알고리즘의 도입 효과를 분석하기 위해 기존 렌탈 서비스 기업의 근무방식을 모방한 세 가지 룰과 비교하는 실험을 수행하였다. 세 가지 룰은 다음과 같다. FCFS(First-Come First-Seivice)는 고객 요구시간의 하한이 가까운 고객을 먼저 처리하는 방식이고, SPT(Shortest Processing Time)는 처리시간이 짧은 고객을 먼저 처리하는 방식이다. 마지막으로, EDD(Earliest Due Date)는 고객 요구시간의 상한이 가까운 고객 순서대로 처리하는 방식이다.

5.2 실험 결과

작은 크기의 실험에 대한 결과는 <Table 3>, 현실적인 크기의 실험 결과는 <Table 4>에 정리하였다. <Table 3>의 obj는 목적함수 값으로 각 인스턴스에 대한 30번 반복 실행의 평균값이다. 제한된 시간 3600초 내에 최적해를 찾지 못하면 N/A로 표시했다. <Figure 5>는 GA, PSO와 룰들의 성능 척도인 RPD에 대한 구간 그림이다. GA과 PSO의 성능을 통계적으로 비교하기 위하여 T 검정을 수행하였다. 총 720회의 시행 결과, GA의 평균 성능은 6.44, PSO의 평균 성능은 10.42로 나타났다. 두 알고리즘의 표준편차는 각각 3.53과 4.27이었다. 평균 성능의 차이는 -3.98로, 99% 신뢰 구간에서는 -3.499로 계산되었다. T 검정 결과, T 값은 -19.28이며, p-값은 0.000으로 매우 낮게 나타나 두 알고리즘의 성능에는 차이가 있는 것으로 확인되었다. 즉, GA가 PSO보다 통계적으로 유의하게 더 우수한 성능을 보임을 시사한다.

Table 3.

Testing Results of Small Size Instances

Table 4.

Testing Results of Large Size Instances

Figure 5.

RPD Mean Plot of Heuristics

5.3 전략의 도입 효과

본 논문의 핵심전략인 고객 정보공유의 효과를 입증하기 위해 추가 실험을 진행한다. 5.2절의 실험결과에서 성능이 가장 좋았던 GA를 고객 정보 공유를 하지 않은 방식과 비교한다. Non_sharing GA는 FCFS 할당규칙을 통해 특정 부분해(고객-방문 서비스원 간의 할당)를 결정한 후, 이 부분해를 기반으로 나머지 부분해 (고객 방문 순서)에 대한 의사결정은 인코딩 해를 통해 진화시키는 유전 알고리즘이다. Non_sharing GA는 5.1절의 실험계획을 따라 24개의 현실적인 크기의 실험을 30회 반복 진행하였다. <Figure 6>은 GA와 Non_sharing GA의 성능 척도인 RPD에 대한 구간 그림이며 해당 결과 고객 공유를 고려한 GA의 성능이 더 우수하다. 추가로 <Table 5>는 GA와 Non_sharing GA의 T 검정 결과로 신뢰수준 99%에서 유의했다.

Figure 6.

RPD Mean Plot of Sharing GA and Non_Sharing GA

Table 5.

T-tset results of Sharing GA and Non_Sharing GA

제안한 전략의 도입 효과를 분석하기 위하여 기업의 총비용 측면과 방문 서비스원들의 수익 개선 측면에서 실험 결과를 살펴보고자 한다. <Table 4>에서 임의 방식 3가지 중 가장 성능이 좋았던 18번 인스턴스에서의 FCFS를 살펴보고, 제안한 GA와의 비교를 진행한다. 5장의 실험에서 기업 운영비용으로 유류비, 시간어김비용, 추가근무수당, 그리고 미충족수당이 모두 포함되었다. 그러나 미충족수당은 현실에서 실제로 존재하는 비용이 아닌, 서비스원들의 최저임금에 못 미치는 금액을 보장해준다는 임의 개념으로, 본 연구에서 운영 전략 제시를 위해 추가적으로 고려한 비용이다. 현실에서는 서비스원의 시간 대비 수익을 보장하기 위해 건당 수수료 인상의 방법이 고려된다. 따라서, FCFS에서 서비스원의 시간 대비 수익을 보장하기 위한 건당 수수료 인상의 정도를 파악해본 결과 약 2,600원의 인상이 필요하다고 판단된다. 하지만 기업은 현실적으로 서비스원의 소득을 보장하기 위한 미충족수당의 비용 인상분을 전혀 반영하고 있지 않다. 제안한 GA에서는 미충족수당과 추가근무수당을 모두 보장하고 있으며, 총비용 측면에 있어서 이를 고려하지 않는 FCFS 방법의 총비용보다 작은 효과적인 근무자 경로계획을 수립한다.

<Figure 7>에서는 GA와 FCFS의 총비용 비교 그래프를 보여주고 GA의 총비용 측면에서의 상대적 우수성을 입증하고자 한다. GA는 FCFS와 비교하였을 때, 방문 서비스원의 희망근무시간을 고려하기에 추가근무수당이 발생했지만, 유류비와 시간어김비용의 감소로 인하여 결과적으로 총비용을 6% 감소시켰다. 그럼에도 서비스원의 시간 대비 수익에 충족되지 못한 금액에 대해 미충족수당을 지급했다. 따라서, 제안한 GA는 기업이 건당 서비스 수수료를 인상하지 않고도 줄어든 비용으로 방문 서비스원의 시간 대비 수익을 보장하며, 기업의 총 운영비용도 감소시키는 효과를 보임을 알 수 있다.

Figure 7.

Total cost graph of FCFS and GA

6. 결 론

본 논문에서는 렌탈 서비스 기업의 지속가능성 증대를 위해 방문 서비스원 이탈 문제를 해결하는 새로운 운영전략을 제시한다. 이를 바탕으로, 방문 서비스원들의 근무시간과 고객의 요구시간을 모두 고려하는 방문 서비스원 경로계획문제를 다루었다. 본 연구에서 제시한 서비스원 경로계획문제는 방문 서비스원의 소득 보장 및 자유도를 고려한 미충족수당과 추가근무수당, 그리고 고객 만족도를 고려한 시간어김비용, 유류비를 최소화하는 것을 목적으로 서비스원의 서비스 제공 고객 할당, 방문순서, 그리고 방문시간을 동시에 결정한다. 주어진 문제의 효율적 해결을 위하여 혼합정수선형계획법을 수립하고, 현실 크기 문제를 해결하기 위해 유전 알고리즘과 입자 군집 최적화 알고리즘을 제시했다. 기존의 스케줄링 방식을 모방한 세 가지 룰과 비교하였을 때 제안한 운영전략이 효과적으로 적용되었음을 확인하였다.

하지만 방문 서비스원의 근무방식이 담당 고객의 상황에 따라, 서비스원의 성향에 따라 모두 다르기 때문에 제안한 운영전략과, 임의로 설정한 세 가지 방식이 이를 모두 고려하지는 못한다. 추후 연구에서 서비스원 및 고객 설문조사를 통해 렌탈 서비스 기업의 운영 방식 개선에 있어서 더 나은 결과를 도출할 것이다.

Acknowledgments

이 논문은 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임(No. NRF-2022R1F1A1068304). 이 연구는 대한산업공학회 대학생 프로젝트 경진대회 수상작품을 바탕으로 수행됨.

References

• Allaham, H.and Dalalah, D. (2022), MILP of multitask scheduling of geographically distributed maintenance tasks, International Journal of Industrial Engineering Computations, 13(1), 119-134. [https://doi.org/10.5267/j.ijiec.2021.7.001]
• Arias-Melia, P., Liu, J., and Mandania, R. (2022), The vehicle sharing and task allocation problem: MILP formulation and a heuristic solution approach, Computers & Operations Research, 147. [https://doi.org/10.1016/j.cor.2022.105929]
• Baker, K. R. and Keller, B. (2010), Solving the single-machine sequencing problem using integer programming, Computers & Industrial Engineering, 59(4), 730-735. [https://doi.org/10.1016/j.cie.2010.07.028]
• Bazirha, M., Benmansour, R., and Kadrani, A. (2023), An efficient two-phase heuristic for the home care routing and scheduling problem, Computers & Industrial Engineering, 181. [https://doi.org/10.1016/j.cie.2023.109329]
• Braekers, K., Hartl, R. F., Parragh, S. N., and Tricoire, F. (2016), A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience, European Journal of Operational Research, 248(2), 428-443. [https://doi.org/10.1016/j.ejor.2015.07.028]
• Burke, E. K., de Werra, D., Landa Silva, J. D., and Raess, C. (2004), Applying Heuristic Methods to Schedule Sports Competitions on Multiple Venues, In Proceedings PATAT, 2004, 451-456.
• Choi, J. S. (2022, July), Coway Coordination is a Worker...Another ruling recognizing special jobs, The Korea Economic Daily, Retrieved September 25, 2023, from https://www.hankyung.com/article/2022072940501, .
• Ebrahimi, M. A., Dehnavi, H. D., Mirabi, M., Honari, M. T., and Sadeghian, A. (2022), Solving NP hard problems using a new genetic algorithm, International Journal of Nonlinear Analysis and Applications, 14(1), 275-285.
• Errico, F., Desaulniers, G., Gendreau, M., Rei, W., and Rousseau, L. M. (2018), The Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times, EURO Journal on Transportation and Logistics, 7, 223-251. [https://doi.org/10.1007/s13676-016-0101-4]
• Eshtehadi,  R., Demir, E., and Huang, Y. (2020), Solving the vehicle routing problem with multi-compartment vehicles for city logistics, Computers & Operations Research, 115. [https://doi.org/10.1016/j.cor.2019.104859]
• Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., and Raidl, G. R. (2015), Metaheuristics for solving a multimodal home-healthcare scheduling problem, Central European Journal of Operations Research, 23, 89-113. [https://doi.org/10.1007/s10100-013-0305-8]
• Iswari, T. and Asih, A. M. S. (2018), Comparing genetic algorithm and particle swarm optimization for solving capacitated vehicle routing problem, IOP Conference Series: Materials Science and Engineering, 337(1), 12004. [https://doi.org/10.1088/1757-899X/337/1/012004]
• Jung, S. M. (2021), A Study on the Development and Application of Competency Model for Retal Service Home-visit Employees (Master’s thesis), Hanyang University, Korea.
• Kim, D. J. (2023, April), Domestic Rental Market Expected to Reach 100 Trillion Won by 2025…Entering an Era Where Even Restaurant Startups are Possible Through Rentals, The Stock, Retrieved September 25, 2023, from https://www.the-stock.kr/news/articleView.html?idxno=18158, .
• Kim, Y. G. (2022, April), Coway Faces ‘Service Worker’ Strike…Consumer Inconvenience Unavoidable, The Maeil Shinmun, Retrieved September 25, 2023, from https://n.news.naver.com/article/088/0000755480, .
• Korcyl, A., Ksiazek, R., and Gdowska, K. (2019), A MILP model for the municipal solid waste selective collection routing problem, Decision Making in Manufacturing and Services, 13(1-2), 17-35. [https://doi.org/10.7494/dmms.2019.13.1-2.3470]
• Lee, J. A. (2019), A Study on the Logistic service Quality Classification and Customer Satisfaction of Daily Living Supplies Rental company, Korea International Commerce Review, 34(3), 167-190. [https://doi.org/10.18104/kaic.2019.34.3.167]
• Li, L., Chen, Y., and Meng, J. (2020), Improved Tabu Search Algorithm for Solving the Vehicle Routing Problem with Soft Time Windows in B2C Environment, 2020 Chinese Control And Decision Conference (CCDC), 3629-3633. [https://doi.org/10.1109/CCDC49329.2020.9164444]
• Li, X., Tian, P., and Leung, S. C. H. (2010), Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm, International Journal of Production Economics, 125(1), 137-145. [https://doi.org/10.1016/j.ijpe.2010.01.013]
• Liu, R., Xie, X., Augusto, V., and Rodriguez, C. (2013), Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, European Journal of Operational Research, 230(3), 475-486. [https://doi.org/10.1016/j.ejor.2013.04.044]
• Nickel, S., Schröder, M., and Steeg, J. (2012), Mid-term and short-term planning support for home health care services, European Journal of Operational Research, 219(3), 574-587. [https://doi.org/10.1016/j.ejor.2011.10.042]
• Pan, Q., Tasgetiren, M. F., and Liang, Y. (2008), A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Computers & Operations Research, 35(9), 2807-2839. [https://doi.org/10.1016/j.cor.2006.12.030]
• Pureza, V., Morabito, R., and Reimann, M. (2012), Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW, European Journal of Operational Research, 218(3), 636-647. [https://doi.org/10.1016/j.ejor.2011.12.005]
• Salani, M. and Battarra,  M. (2018), The opportunity cost of time window violations, EURO Journal on Transportation and Logistics, 7(4), 343-361. [https://doi.org/10.1007/s13676-018-0121-3]
• Seong, J. (2006), Vehicle Routing Problem with Time Windows considering Outsourcing Vehicles, Journal of Korean Institute of Industrial Engineers, 32(2), 91-97.
• Tsang, M. Y. and Shehadeh, K. S. (2023), Stochastic optimization models for a home service routing and appointment scheduling problem with random travel and service times, European Journal of Operational Research, 307(1), 48-63. [https://doi.org/10.1016/j.ejor.2022.09.020]
• Wirnitzer, J., Heckmann, I., Meyer, A., and Nickel, S. (2016), Patient-based nurse rostering in home care, Operations Research for Health Care, 8, 91-102. [https://doi.org/10.1016/j.orhc.2015.08.005]