It　is　expected　that　mobile　parcel　lockers　(MPLs)　will　provide　more　responsive　and　flexible　service　to　the　increasing　variation　of　demand　than　fixed　parcel　lockers.　However,　the　service　provided　by　MPLs　following　planned　routes　can　be　degraded　and　even　fail　due　to　the　demand　uncertainty,　such　as　demand　volume　and　pickup　time.　In　this　study,　we　propose　an　optimization　approach　integrated　with　the　recourse　strategies　to　overcome　this　barrier.　Three　types　of　uncertain　demands　and　two　types　of　service　failures　are　addressed　in　this　study,　with　consideration　of　uncertain　demands　and　time　window　constraint.　To　optimally　determine　the　a　priori　routes　for　a　set　of　MPLs,　we　propose　a　tailored　tabu　search　algorithm　by　taking　into　account　the　recourse　cost.　A　series　of　numerical　experiments　were　conducted　to　examine　the　effectiveness　of　the　proposed　approach　in　enhancing　route　reliability　with　a　comparison　to　ordinary　express　vehicles.　The　results　reveal　that　the　service　reliability　can　be　significantly　improved　with　only　a　marginal　increase　in　the　operational　cost　by　the　proposed　approach.　©　2024