近年運送業界では自動搬送車（AGV）や電気自動車（EV），ドローンなどが使用されることが多くある．複数の顧客を効率的に訪問するために，時間や距離の最小化など様々な目的に合わせた訪問ルートを構築する手法が多数提案された．ここで，一般的な場合バッテリーを持ち電力を動力源にすることから，どのタイミングで，どの程度充電するかの2点を追加で考慮する必要がある．本研究では複数の充電ポイントと，ある訪問ルートが与えられたときに，そのルートに最適な充電計画を含めたものを生成する多項式時間の手法を提案する．