본 논문은 전기차(EV) 기반의 차량 호출 배달 서비스와 같은 현대 서비스 시스템에서 증가하는 EV의 통합과 V2G 기술의 발전으로 인해 발생하는 최적화 문제를 다룹니다. EV의 주행 거리 제한과 동적인 전기 요금을 고려하여 고객 요청을 수행하면서 충전 또는 방전 시점 및 장소를 결정하는 수익 극대화 문제인 EVOP-V2G(Electric Vehicle Orienteering Problem with V2G)를 제시합니다. 혼합 정수 계획법(MIP) 모델로 문제를 공식화하고, 진화 알고리즘(EA)과 대규모 이웃 탐색(LNS) 기반의 두 가지 준 최적 메타 휴리스틱 알고리즘을 제안합니다. 실제 데이터를 사용한 실험 결과, 제안된 알고리즘은 기준선 대비 운전자 수익을 두 배로 증가시키는 동시에, 작은 인스턴스에서는 준 최적 성능을, 큰 인스턴스에서는 우수한 확장성을 보입니다.