Nonlinear advection-diffusion equations often arise in the modeling of transport processes. We propose for these equations a non-overlapping domain decomposition algorithm of Schwarz waveform-relaxation (SWR) type. It relies on nonlinear zeroth-order (or Robin) transmission conditions between the sub-domains that ensure the continuity of the converged solution and of its normal flux across the interface. We prove existence of unique iterative solutions and the convergence of the algorithm. We then present a numerical discretization for solving the SWR problems using a forward Euler discretization in time and a finite volume method in space, including a local Newton iteration for solving the nonlinear transmission conditions. Our discrete algorithm is asymptotic preserving, i.e., robust in the vanishing viscosity limit. Finally, we present numerical results that confirm the theoretical findings, in particular the convergence of the algorithm. Moreover, we show that the SWR algorithm can be successfully applied to two-phase flow problems in porous media as paradigms for evolution equations with strongly nonlinear advective and diffusive fluxes.